[LeetCode/Top Interview 150] [Divide & Conquer] 148. Sort List

문제 링크: https://leetcode.com/problems/sort-list/?envType=study-plan-v2&envId=top-interview-150
사용 언어: Java(OpenJDK 17. Java 8)

난이도: medium

문제:

Given the head of a linked list, return the list after sorting it in ascending order.

Example 1:

Input: head = [4,2,1,3]
Output: [1,2,3,4]

Example 2:

Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]
Example 3:

Input: head = []
Output: []

Constraints:

The number of nodes in the list is in the range [0, 5 * 10^4].
-10^5 <= Node.val <= 10^5

Follow up: Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?

전략:

주어진 ListNode를 헤드 기준으로 정렬하는 문제이다.

추가: 이 리스트를 O(n logn) 시간과 O(1) 공간(상수)만 사용해 정렬해보세요.

먼저 ListNode들을 순회하며 전체 요소를 배열에 저장하고, 배열로 병합정렬하여 문제를 푼다.
일단은 효율 생각하지 않고 푸는 것이 중요할 듯.

코드 구현:

/**
 * 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 sortList(ListNode head) {        
        // 전체 요소 저장용
        ArrayList<ListNode> list = new ArrayList<>();
        // 시작 노드
        ListNode next = head;
        // [] 빈 노드 받는 경우 예외처리
        if (head==null || head.next == null) { return head; }
        // Node 순회하며 list에 추가
        while (next != null) {
            list.add(next);            
            next = next.next;
        }

        // 정렬용 배열
        ListNode[] result = new ListNode[list.size()];
        // 배열로 값 복사
        for (int i=0;i<list.size();i++) {
           result[i] = list.get(i);
        }

        //정렬(재귀) 호출
        sort(result, 0, result.length-1);

        // 정렬 결과 Node에 반영
        for (int i=0;i<result.length-1;i++) {
           result[i].next = result[i+1];
        }
        result[result.length-1].next=null;

        return result[0];
    }

    public void sort(ListNode[] array, int start, int end) {
        // 정렬 범위
        if (start < end) {
            int half = (end+start)/2;
            
            sort(array,start,half); // 절반씩 정렬
            sort(array,half+1,end); // 머지 정렬
            merge(array,start,half,end); // 정렬된 배열 2개 병합
        }
    }

    public void merge(ListNode[] array, int start, int half, int end) {
        int i = start, j = half+1, k = start;
        ListNode[] tmp = new ListNode[array.length];

        while(i<=half && j<=end) { // 두 배열 모두 범위 체크
            // 좌측 배열 값이 더 작으면
            if(array[i].val <= array[j].val) {
                tmp[k++] = array[i++]; // 임시배열에 좌측 값 복사
            }
            else tmp[k++] = array[j++]; // 임시배열에 우측 값 복사
        }
        // 좌측 배열에 아직 복사할 값이 남은 경우 복사
        while(i<=half) tmp[k++] = array[i++];
        // 우측 배열에 아직 복사할 값이 남은 경우 복사
        while(j<=end) tmp[k++] = array[j++];
        // 임시 배열에 있던 값 가져오기
        for(int a = start; a<=end; a++) array[a] = tmp[a];
    }
}
Time: 628 ms (5.03%), Space: 53.7 MB (98.33%) - LeetHub

실행결과:
https://github.com/1-vL/LeetCode/blob/main/0148-sort-list/0148-sort-list.java

개선 방안:

일단 푸는데 집중한 만큼 시간 복잡도가 처참하다.
ArrayList -> 배열로 바꾸는 과정 같은 부분을 없애고 바로 연결을 따라가며 풀 수 있도록 고치면 훨씬 빨라질 수 있을 것 같다. 다만 실제로 어떻게 하면 자료구조를 추가로 사용하지 않고 절반을 찾을 수 있을지 모르겠다.

Solutions 탭의 타인 코드:

public class Solution {
    
    //merge two sorted list, return result head
    public ListNode merge(ListNode h1, ListNode h2){
        if(h1 == null){
            return h2;
        }
        if(h2 == null){
            return h1;
        }
        
        if(h1.val < h2.val){
            h1.next = merge(h1.next, h2);
            return h1;
        }
        else{
            h2.next = merge(h1, h2.next);
            return h2;
        }
        
    }
    
    public ListNode sortList(ListNode head) {
        //bottom case
        if(head == null){
            return head;
        }
        if(head.next == null){
            return head;
        }
        
        //p1 move 1 step every time, p2 move 2 step every time, pre record node before p1
        ListNode p1 = head;
        ListNode p2 = head;
        ListNode pre = head;
        // 2칸씩 전진하는 포인터와 1칸씩 전진하는 포인터로 나눠 절반 지점을 찾는 건 천재적인 것 같다.
        
        while(p2 != null && p2.next != null){
            pre = p1;
            p1 = p1.next;
            p2 = p2.next.next;
        }
        //change pre next to null, make two sub list(head to pre, p1 to p2)
        pre.next = null;
        // 절단 지점에서 끊기
        
        //handle those two sub list
        ListNode h1 = sortList(head);
        ListNode h2 = sortList(p1);
        
        return merge(h1, h2);
        
    }
    
}
Time: 13 ms (34.37%), Space: 57.3 MB (5.2%) - LeetHub

회고:

ListNode에 익숙치 않아 입출력 단계부터 고생이었다.
역시 직접 순회를 하니 시간 복잡도가 훨씬 좋아진 것 같다.
포인터 2개로 나눠서 절반지점 찾는 방법은 기억해 둘 필요가 있겠다.
일단 냅다 푼 만큼 나중에 다시 한 번 제대로 풀어봐야겠다.