[DS] Reverse a doubly-linked list

양방향 연결 리스트 (순환X)의 방향을 바꾸는 코드를 작성해야 한다.

www.hackerrank.com/challenges/reverse-a-doubly-linked-list/problem

 

DoublyLinkedListNode* reverse(DoublyLinkedListNode* head) {
    DoublyLinkedListNode *link = malloc(sizeof(DoublyLinkedListNode));
    DoublyLinkedListNode *rever = malloc(sizeof(DoublyLinkedListNode));
    DoublyLinkedListNode *tmp = head;
    while(tmp ->next != NULL){
        tmp = tmp->next;
    }
    rever = tmp;
    while(1){
        link=tmp->prev;
        tmp->prev = tmp->next;
        tmp->next = link;
        if(tmp == head){
            break;
        }
        else{
            tmp = tmp->next;
        }
    }
    return rever;

}

△ 작성한 부분

우선 리스트의 가장 마지막 원소까지 접근한다. 그 노드는 reverse 한 리스트의 head 노드가 되기 때문에 따로 저장한다.reverse 리스트의 head 노드부터 양방향 노드의 순서를 바꾼다. 그리고 원래 리스트의 head 노드에 도달하기 전까지는 계속 앞쪽으로 나아가야 하기 때문에 reverse 된 상태에서의 next 노드로 접근해 반복한다.