[LeetCode] Reorder List (Java)

✉️문제

https://leetcode.com/problems/reorder-list/description/

Reorder List - LeetCode

 

📝 접근 

이 문제는 합병 정렬에 대한 기본적인 원리를 담고 있다. 먼저 어떻게 순서를 나열하는지 예제를 통해 알아보자. 

(홀수 일 때) 1 -> 2 -> 3 -> 4   ========>  1 -> 4 -> 2 -> 3 
(짝수 일 때) 1 -> 2 -> 3 -> 4 -> 5    ========>  1 -> 5 -> 2 -> 4 -> 3

규칙을 찾기 위해 노드를 분리해보면 절반을 기준으로 first, second로 나눌 수 있으며, second 리스트는 마지막 노드에서 시작해서 거꾸로 이동한다.

(first) 1, 2, 3
(second) 4, 5 

이렇게 코드를 절반으로 나누기 위해서 분할 과정을 거친다. 분할을 하기 위해 first는 노드를 한 번 이동하고 second는 두 번 이동시킨다. 이렇게 하면 리스트를 절반으로 나눌 수 있다.

ListNode slow = root;
ListNode fast = root.next;

while(fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
}

 

리스트를 절반으로 분리했으니 이제 second의 리스트 방향을 반대로 바꿔주어야 한다. 그런데 ListNode는 단방향으로 설정되어 있어 이전 값을 알 수가 없다. 즉 5의 이전 값이 4인지 알 수 없다. 

하지만 우리는 위의 분리 과정을 거치면서 second 리스트의 시작 노드가 어딘지 알 수 있다. (slow.next) 따라서 second리스트의 첫 노드부터 시작해서 방향을 반대로 바꾸어 간다.

// 두 번째 배열 순서 바꾸기 
ListNode second = slow.next;
ListNode prev = null;
slow.next = null;
while(second != null) {
    ListNode next = second.next;
    second.next = prev;
    prev = second;
    second = next;
}

마지막으로 first, second 리스트를 합병해준다.

// 합병
ListNode first = head;
second = prev;
while(second != null) {
    ListNode tmp = first.next;
    ListNode tmp2 = second.next;
    first.next = second;
    second.next = tmp;
    first = tmp;
    second = tmp2;
}

 

🗝 문제풀이

class Solution {
    public void reorderList(ListNode head) {
        ListNode slow = head;
        ListNode fast = head.next;

        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // 두 번째 배열 순서 바꾸기 
        ListNode second = slow.next;
        ListNode prev = null;
        slow.next = null;
        while(second != null) {
            ListNode next = second.next;
            second.next = prev;
            prev = second;
            second = next;
        }

        // 합병
        ListNode first = head;
        second = prev;
        while(second != null) {
            ListNode tmp = first.next;
            ListNode tmp2 = second.next;
            first.next = second;
            second.next = tmp;
            first = tmp;
            second = tmp2;
        }
    }
}