Linked List | Reverse Linked List

Given the head of a singly linked list, reverse the list, and return the reversed list.

말 그대로, head노드를 가지고 Linked List를 reverse해서, 새로운 head를 리턴하는 문제다. 모두 오른쪽을 바라보다가, 순차적으로 왼쪽을 바라보게 하는 그림을 연상시킨다. 이 문제를 한큐만에, O(N)으로 푸는 방법이 있다. 바로 지나가면서 뒤집는 방법이다. 코드는 다음과 같다.

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode newNext = null;
        ListNode temp = null;
        ListNode curr = head;
        while(curr != null){
            temp = curr.next;
            curr.next = newNext;
            newNext = curr;
            curr = temp;
        }
        return newNext;
    }
}

* Time Complexity: O(N), Linked List의 크기만큼 정확하게 1회 돈다.

* Space Complexity: O(1), 3개의 노드 포인터를 사용했다.

 

로직은 간단하다.

1. newNext, temp의 값을 null로 지정해준다.

2. 현재 작업중인 노드를 의미하는 curr는 head부터 시작한다 (head를 사용해도 무관하다).

3. curr 포인터가 맨 마지막 노드를 지나 null에 도달할때까지 while룹을 돌리는데,

- curr의 다음 노드 정보를 temp로 지켜둔다

- 지켜두었으니 안심하고 curr의 다음을 newNext로 지정해준다. 

- newNext를 다음번 loop을 위해 curr가 가르키는 노드로 옮긴다.

- curr를 임시 저장해두었던 temp을 이용해서 다음 노드로 움직인다.

4. while loop을 빠져나왔다는건? newNext가 기존 마지막 노드, 새로운 리스트에선 첫번째 노드를 가르키고 있다는 뜻이다. 리턴해준다.

 

이 해법으로 풀었을 때, 최상의 스피드와 메모리 사용으로 문제를 풀 수 있었다.

 

 

ㄹ 형태의 포켓몬 Linked List가 반대로 정렬된다면? 정답: 너무 귀여울것 같다.

.....

temp = curr.next // 어니부기;
curr.next = newNext; // null
newNext = curr // 꼬부기
curr = temp; // 어니부기

temp = curr.next // 이브이
curr.next =  nextNext; //꼬부기
newNext = curr // 어니부기
curr = temp; // 이브이

.....

 

Reference

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

Reverse Linked List - LeetCode