[LeetCode#148] Sort List

❒ Description

---

날짜	2024.09.27 (금)
레벨	Medium
제목	Sort List
링크	https://leetcode.com/problems/sort-list/description/
자료구조
알고리즘	정렬
시간 복잡도	O(nlogn)

 

 

 

 

 

❒ 문제 분석

---

시간 복잡도 O(nlogn) 으로 풀어야하는 제약이 있는 문제다. 따라서 병합 정렬을 사용해야 한다.

먼저 병합 정렬의 분할 정복을 위해서는 중앙을 분리해야 한다. 이 문제는 LinkedList를 사용하고 있고,

이 자료 구조는 배열의 길이를 알 수 없다. 따라서 Runner 기법을 사용해야 한다.

 

마지막에는 정복(Conquer)하는 과정이 필요한데, 이 때 오름차순으로 정복해야 한다.

1	c1 = `-1 > 5`	c2 = `0 > 3 > 4`	c1.val > c2.val (false)	return -1 > 0 > 3 > 4 > 5 > null
2	c1 = `5 > null`	c2 = `0 > 3 > 4`	c1.val > c2.val (true)	return 0 > 3 > 4 > 5 > null
	c1 =`0 > 3 > 4`	c2 = `5 > null`
3	c1 = `3 > 4`	c2 = `5 > null`	c1.val > c2.val (false)	return 3 > 4 > 5 > null
4	c1 = `4 > null`	c2 = `5 > null`	c1.val > c2.val (false)	return 4 > 5 > null
5	c1 = `null`	c2 = `5 > null`	c1 == null	return 5 > null

 

 

 

 

 

❒ 문제 분석

---

public ListNode sortList(ListNode head) {
    // 예외 처리
    if (head == null || head.next == null) return head;
    
    // Runner 기법
    ListNode half = null, slow = head, fast = head;
    while (fast != tail) {
        half = slow;
        slow = slow.next;
        fast = fast.next.next;
    }
    
    // 중앙 지점 연결 끊기
    half.next = null;
    
    // Divide
    ListNode chunk1 = sortList(head, slow);
    ListNode chunk2 = sortList(slow.next, tail);
    
    // Conquer
    reteurn mergeSortChunks(chunk1, chunk2);
}

private ListNode mergeSortChunks(ListNode chunk1, ListNode chunk2) {
    if (chunk1 == null) return chunk2;
    if (chunk2 == null) return chunk1;
    
    if (chunk1.val > chunk2.val) {
        ListNode temp  = chunk2;
        chunk2 = chunk1;
        chunk1 = temp;
    }
    chunk1.left = mergeSortChunks(chunk1.next, chunk2);
    return chunk1;
}

 

 

 

 

 

 

---