LeetCode 206(Reverse Linked List, java)

0. 문제

https://leetcode.com/problems/reverse-linked-list/

Reverse Linked List - LeetCode

 

1. 문제 설명

- 문제에서 연결 리스트(head)가 주어진다.

- 해당 연결 리스트를 역순으로 재 정렬해서 반환하는 것이 문제의 핵심이다. 

 

2. 문제 해설

- 이 문제는 연결 리스트라는 자료구조의 특성과 재귀 함수를 이해하고 있어야 풀 수 있는 문제다.

 

a) 첫 번째 접근

- 사실 가장 간단한 방법으로는 연결 리스트(head)의 반복적인 탐색을 수행하면 된다.

- 가장 마지막 노드(head.next == null)를 찾은 뒤, 해당 노드를 새로운 연결 리스트에 삽입하는 방식으로 해결할 수 있다.

- 하지만 이 방식은 전체 N개의 노드를 N번 탐색해야 하므로 O(n^2)의 시간 복잡도를 갖는다.

- 이는 효율적인 방식이 아니다. 

 

- 이처럼 필수 불가결한 반복적인 작업을 효율적으로 수행하기 위해서는 어떤 방법을 사용해야 할까?

- 이런 경우에 재귀 함수를 사용하는 것이다. 

 

b) 두 번째 접근

- 이제 재귀 함수 내부에서 반복 수행할 작업의 내용을 판단해야 한다.

- 예를 들어,  1 → 2 → 3 → 4 → 5의 순서를 갖는 연결 리스트를 역순으로 정렬한다고 해보자. 

 

- 우선 역순의 연결 리스트를 저장할 공간이 필요하므로, 새로운 연결 리스트(newHead)를 생성한다.

- 해당 연결 리스트(newHead)는 매번 새롭게 생성하지 않고 계속해서 사용할 객체이다.

- 그러므로 재귀 함수의 매개변수로 사용한다. 

 

- newHead의 초기값은 null로 설정한다. 그 이유는 다음과 같다. 

 

  → 현재 문제에서 주어지는 ListNode 클래스는 next 속성을 이용해 다음 노드만을 접근 및 설정할 수 있다.

  → 그러므로 newHead에 저장되는 노드는 어떤 노드의 다음 노드가 되어야 한다.

  → 즉, 첫 번째로 삽입되는 노드가 가장 마지막 순서에 위치한다.

  → 그러므로 newHead에서 가장 마지막에 위치한 노드의 next 값은 null이 되어야 한다. 

 

- 이와 같은 이유로 newHead의 초기 값은 null이 되어야 한다. 

 

c) 세 번째 접근

- newHead의 가장 첫 번째 삽입될 노드는 역순으로 정렬 시 가장 마지막에 위치한 노드가 된다.

- 그러므로 1이 가장 첫 번째로 삽입될 노드가 된다.

 

- 그렇다면 head의 첫 번째 노드(= 1)의 다음 값은 newHead(= null)이 된다.(1 → null)

- 즉, 다음 노드(= 2)와의 연결이 끊긴다.

 

- 그러나 이렇게 하면 기존의 head를 계속해서 탐색할 수 없다.

- 그러므로 연결을 끊기 전에 다음 노드(2 → 3 → 4 → 5)를 새로운 연결 리스트(nextNode)를 만들어 보관한다.

 

d) 네 번째 접근 

- 세 번째 접근에서 첫 번째 노드(= 1)의 다음 값을 newHead로 만들었다.(1 → null)

- 이제 newHead를 경신한다. (newHead = 1 → null)

 

e) 다섯 번째 접근

- 계속해서 연결 리스트를 탐색해야 하므로 head의 값을 nextNode로 경신한다. 

 

- 여기까지의 과정을 재귀 함수로 반복한다. 

- 다음 코드를 보면서 이해해보자. 

 

3. 정답 코드

class Solution {
    public ListNode reverseList(ListNode head) {
        return changeDirection(head, null);
    }
    
    public ListNode changeDirection(ListNode head, ListNode newHead) {
        
        if(head == null) {
            return newHead;
        }
        
        ListNode nextNode = head.next; // 2 -> 3 -> 4 -> 5
        head.next = newHead; // 1 -> null
        newHead = head; // 1 -> null
        head = nextNode; // 2 -> 3 -> 4 -> 5
        
        return changeDirection(head, newHead);
    }
}