206. Reverse Linked List (Java, LinkedList, Leetcode)

이 문제의 핵심은 방향 지정과 값을 별개로 보는 것이다.

방향과 값은 전혀 다른 속성으로 방향도 바꿔주고 값도 바꿔주는 2가지 작업을 일련적으로 해야하는 것이다.

 

1. 이전 값을 담을 노드를 하나 선언한다. Linked List에서 마지막 노드는 null을 가르키기 때문에 이 새로운 노드도 null로 선언한다. 

 

2. head가 존재하는 동안에 라는 제한 조건을 걸어준다. 1번에서 말했듯이 마지막 노드는 null을 가르키기 때문에 null이라면 마지막에 도달했다는 의미를 가진다.

2-1. 마지막 head에서도 작업을 해야 reverse가 되기 때문에 head.next가 아닌 head가 null인 경우를 체크한다.

 

방향

3. 현재 노드의 다음 노드를 저장한 후에 현재 노드가 1번 노드를 바라보게 한다. 

3-1. 다음 노드는 현재 노드의 방향과 다음 값까지 전부 저장되는 값이다.

 

값

4. 현재 노드의 값을 1번 새로운 노드에 옮겨 담는다. 

4-1. 3번에서 저장한 다음 노드의 값을 현재 노드에 담는다.

 

간단하게 요약하자면 다음과 같다.

 

이전 값이 담길 노드 선언. 현재 노드의 다음 노드와 연결을 끊기 위해 다음 노드 저장. 현재 노드가 이전 노드를 바라보게 하기. 이전 노드를 현재 노드로, 다음 노드를 현재 노드로 변경.

 

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