206. Reverse Linked List (Leetcode)

 

Naive Approach로는, ArrayList를 하나 선언해서 LL 를 순회하면서 해당 ArrayList에 원소를 모두 넣은 후, 다시 거꾸로 ArrayList를 순회하면서 링크드리스트를 만들 수 있는 방법이 있지만, Space 를 불필요하게 사용한다.

그러므로 Singly LinkedList 를 in-place 로 Reverse 시켜보자.(공간 낭비 ㄴㄴ)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {        
        ListNode prev = null; // 1
        ListNode curr = head; // 2
        while(curr!=null) { // 3
            ListNode nextTemp = curr.next; // 4
            curr.next = prev; // 5
            prev = curr; // 6
            curr = nextTemp; // 7
        }
        return prev; // 8
    }
}

각 라인에 대한 정확한 설명을 해보자

각 라인 설명에 앞선 main 아이디어는, prev 와 nextTemp를 이용해, 1. 다음 노드는 temp 에 저장하고, 2.현재 노드는 이전 prev노드를 가리키도록 설정해주고, 3. 이전 노드와, 현재 노드를 각각 다음 한칸씩으로 옮겨주는것이다.

다음은 라인에 대한 정확한 설명

1. prev 는 처음에 null로 초기화 해준다. 왜냐하면, head노드를 순회할 때 현재 노드가 처음으로 가리킬 노드는 결국 reverse했을때의 마지막 노드이기 때문에, prev(null)을 가리킬 것이다. 

2. head 노드를 이동시키지 않고, curr에 head를 할당 시킨 후, curr 포인터를 옮겨두고자, curr를 새로 선언했다. 어차피 head 를 추가로 사용할 일이 없으므로, curr선언하지않고, head로 풀어도 무방하다.

3. curr 현재 노드가 null 이 아닐 때까지, 계속해서 순회해준다. 

4. (여기서부터 중요) 현재 노드의 다음 노드를 nextTemp로 미리 저장해준다. nextTemp를 미리 저장하는 이유는, 현재 노드가 이전노드를 가리키기 이전에, 다음노드에 대한 정보를 저장하고 있어야, loop 문 안에서 curr노드 자체를 다음 노드로 이동시킬수 있기 때문이다.

5. 현재 노드의 다음노드가 이전노드를 가리키게 설정해준다. (curr.next = prev)

6. 이전 노드를 한칸 다음 노드로 이동시킨다. 즉, 이전노드가 curr노드로 되는 것이다. 

7. curr노드는 비로소 nextTemp 노드로 할당하여 다음노드로 한칸을 이동시킨다. 

 

이러면, TC: O(N), SC: O(1) 으로 끊을 수 있음