Problem
Linked List 의 root 가 주어지면 뒤집은 Linked List 의 root 를 구하는 문제입니다.
Solution
문제를 푸는 방법은 총 두가지가 있습니다.
재귀와 반복입니다.
처음에 생각할 수 있는 건 재귀인데 Linked List 의 꼬리까지 쭉 들어간 다음에 node.next 를 변경 하면서 다시 돌아오면 됩니다.
예제를 통해서 어떻게 바뀌는지 알아보겠습니다.
1. 초기 상태
리스트를 끝까지 들어가면 4 부터 시작하게 됩니다 (5 는 head.next == null 이라서 빠져나옴)
2. head.next.next = head;
head.next.next 가 head 를 가리키게 만들어서 4 와 5 는 서로를 가리키게 됩니다.
3. head.next = null;
head.next 를 null 로 만들면서 가리키는 게 없도록 만듭니다.
여기서 헷갈리는 점이 생길 수 있는데 head.next 를 null 로 만드는건 5 노드를 없애는 게 아닙니다.
말 그대로 4 가 가리키는 노드를 없애는 것이고 5 노드는 여전히 존재하고 주소값도 존재합니다.
4. 첫 번째 함수를 빠져나올 때의 최종 모습
5. 두 번째 함수는 다음과 같은 상태입니다.
4 노드가 가리키는 노드가 없기 때문에 NULL 노드를 가리킨다고 할 수 있습니다.
6. 두 번째 함수를 빠져나올 때의 최종 모습
여기까지 진행하면 3 -> 4 -> 5 가 5 -> 4 -> 3 으로 바뀐 사실을 알 수 있습니다.
이대로 처음 시작했던 루트 노드까지 반복하면 최종적으로 뒤집어진 Linked List 를 구할 수 있습니다.
Java Code
// 1. Recursive
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode result = reverseList(head.next);
head.next.next = head;
head.next = null;
return result;
}
}
// 2. iterative
class Solution {
public ListNode reverseList(ListNode head) {
ListNode parent = null;
while (head != null) {
ListNode current = head;
head = head.next;
current.next = parent;
parent = current;
}
return parent;
}
}Kotlin Code
class Solution {
fun reverseList(head: ListNode?): ListNode? {
return head?.next?.let {
reverseList(it).apply {
head.next.next = head;
head.next = null;
}
} ?: head
}
}'알고리즘 문제 > LeetCode' 카테고리의 다른 글
| [LeetCode Easy] Remove All Adjacent Duplicates In String (Java) (0) | 2020.03.25 |
|---|---|
| [LeetCode Medium] Sort Colors (Java) (0) | 2019.12.12 |
| [LeetCode Easy] Single Number (Java, Kotlin) (0) | 2019.12.11 |
| [LeetCode Easy] Maximum Depth Of Binary Tree (Java, Kotlin) (0) | 2019.12.02 |
| [LeetCode Medium] Add Two Numbers (Java) (0) | 2019.11.24 |