148. Sort List

병합 정렬(Merge Sort) 알고리즘 아이디어를 떠올려야 하는 문제.

병합 정렬은 연결 리스트를 정렬하는 데 적합하며, 시간 복잡도 O(nlog⁡n)와  연결 리스트에서 공간 복잡도를 O(1)로 유지할 수 있습니다.

public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int x) { val = x; }
}

public class Solution {
    public ListNode SortList(ListNode head) {
        if (head == null || head.next == null)
            return head;

        // Step 1. Split the list into two halves
        ListNode mid = GetMiddle(head);
        ListNode left = head;
        ListNode right = mid.next;
        mid.next = null; // 리스트를 두 부분으로 분할

        // Step 2. Sort each half
        left = SortList(left);
        right = SortList(right);

        // Step 3. Merge the sorted halves
        return Merge(left, right);
    }

    private ListNode GetMiddle(ListNode head) {
        if (head == null) return head;

        ListNode slow = head, fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    private ListNode Merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;

        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                current.next = l1;
                l1 = l1.next;
            } else {
                current.next = l2;
                l2 = l2.next;
            }
            current = current.next;
        }

        if (l1 != null) current.next = l1;
        if (l2 != null) current.next = l2;

        return dummy.next;
    }
}

 

• SortList 메서드: 리스트가 빈 경우나 단일 노드인 경우를 체크하고, 그렇지 않으면 리스트를 두 부분으로 나눕니다.
• GetMiddle 메서드: 주어진 리스트의 중간 노드를 찾습니다. 느린 포인터와 빠른 포인터를 사용해 중간을 찾습니다.
• Merge 메서드: 두 개의 정렬된 리스트를 병합합니다. 더미 노드를 사용하여 병합 과정에서의 간단함을 유지합니다.

 

 

List 분할 시,

ListNode left = head;   // left: 1 -> 2 -> 3
ListNode right = mid.next;  // right: 4 -> 5
mid.next = null;  // left becomes: 1 -> 2 -> 3, right becomes: 4 -> 5

mid.next 를  null로 초기화 하는 이유가 중요하다.

리스트를 두 부분으로 물리적으로 나누지 않으면, 재귀적으로 호출된 SortList 함수들이 동일한 리스트를 참조하게 되어 무한 루프에 빠질 수 있습니다. 분할을 통해 각 부분 리스트가 독립적으로 처리되도록 보장하는 것이 중요합니다.