[해커랭크] Reverse a doubly linked list (C++)

문제 링크: www.hackerrank.com/challenges/reverse-a-doubly-linked-list/problem

Reverse a doubly linked list | HackerRank

1. 주의할 점

- Node나 NodeList를 이용하여 해결한다

- 현재 문제에선 전부 구현되어있지만, 직접 함수나 구조체를 구현하는 연습을 기른다

 

2. 구현

- 리버스된 Node를 담는 DoublyLinkedList를 생성한다

- Reverse 함수의 파라미터로 받는 변수가 DoublyLinkedList의 Head를 받았으므로 기존 List의 Tail을 향하도록 Head를 재설정한다

- Head가 Tail을 가르키도록 설정했다면, Head->prev를 이용해서 기존 List의 Tail->Head까지의 Node를 전부 Revlist에 insert한다

- 반환형이 Node이므로, Revlist의 Head를 반환한다

 

/*
 * For your reference:
 *
 * DoublyLinkedListNode {
 *     int data;
 *     DoublyLinkedListNode* next;
 *     DoublyLinkedListNode* prev;
 * };
 *
 */
DoublyLinkedListNode* reverse(DoublyLinkedListNode* head) {
    DoublyLinkedList* revlist = new DoublyLinkedList();
    while(1){
        if(head->next)
            head = head->next;
        else break;
    }
    while(head){
        revlist->insert_node(head->data);
        head = head->prev;
    }
    return revlist->head;
}