[LeetCode # 206] Reverse Linked List

주어진 문제는 위와 같다. 단방향 연결 리스트가 주어졌을 때, 이를 반전시키는 것.

 

문제의 해결 방법은 간단하지만 두 가지 방법으로 풀이가 가능하다. 반복문을 사용하는 방법과 재귀함수를 사용하는 방법.

 

먼저, 반복문을 사용하는 방법은 노드를 앞에서부터 탐색하면서 해당 노드를 새로운 리스트의 헤더 노드로 만드는 방법이다. 새로운 리스트의 헤더 노드를 현재 탐색중인 노드와 연결한 뒤 헤더 노드를 현재 탐색중인 노드로 변경한다. 이러한 방법으로 리스트의 순서를 뒤집을 수 있다.

 

아래는 반복문을 사용한 소스 코드이다.

 

class Solution {
public:
    ListNode *reverseList(ListNode *head) {
        ListNode* reversedHead = nullptr;
        ListNode* tmp = head;
        while (tmp != nullptr) {
            ListNode* next = tmp->next;
            tmp->next = reversedHead;
            reversedHead = tmp;
            tmp = next;
        }
        return reversedHead;
    }
};

다음은 재귀함수를 사용한 방법인데, 노드를 끝까지 먼저 탐색한 뒤 마지막 노드를 반전된 리스트의 헤더 노드로 만든다. 그 뒤 기존의 연결 방향을 반대로 바꾸는 방법으로 문제를 해결한다.

 

아래는 재귀함수를 사용한 소스 코드이다.

 

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !(head->next)) {
            return head;
        }
        ListNode* res = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return res;
    }
};