[알고리즘] LeetCode - Sort List

Sort List - LeetCode

문제 설명

• 연결 리스트의 head가 주어진다.
• 주어진 연결 리스트를 오름차순으로 정렬해야 한다.
• 정렬한 후 head의 값을 반환해야 한다.

문제 해결

• 주어진 연결 리스트를 더이상 나눠지지 않을 때까지 나눈다.
• 나눈 것들을 크기를 비교하면서 병합하여 하나의 연결리스트를 만든다.
• 재귀 함수를 사용해서 위 과정을 수행한다.

시간 복잡도

• O(N log N)

풀이 코드

class Solution {
    public ListNode sortList(ListNode head) {
        head = sort(head);
        return head;
    }

    static ListNode sort(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode start = head;
        ListNode slow = head;
        ListNode fast = head;

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

        ListNode mid = slow.next;
        slow.next = null;


        ListNode left = sort(start);
        ListNode right = sort(mid);
        return merge(left, right);
    }

    static ListNode merge(ListNode left, ListNode right) {
        ListNode mergeHead = new ListNode();
        ListNode lastNode = mergeHead;
        
        while(left != null && right != null) {
            if (left.val < right.val) {
                lastNode.next = left;
                lastNode = left;
                left = left.next;
            } else {
                lastNode.next = right;
                lastNode = right;
                right = right.next;
            }
        }
        
        while(left != null) {
            lastNode.next = left;
            lastNode = left;
            left = left.next;
        }

        while(right != null) {
            lastNode.next = right;
            lastNode = right;
            right = right.next;
        }
        return mergeHead.next;
    }
}

결과

시간	메모리
11 ms	56.7 MB

---

1차 시도

1. 풀이 코드

class Solution {
    public ListNode sortList(ListNode head) {
        if (head != null) {
            head = sort(head);
        }

        return head;
    }

    static ListNode sort(ListNode head) {
        ListNode now = head;

        while(now.next != null) {
            // 현재 노드 값과 다음 노드의 값을 비교해서 현재 노드 값이 크면
            if (now.val > now.next.val) {
                // 다음 노드를 젤 앞으로 보냄
                ListNode temp = now.next;
                now.next = temp.next;
                temp.next = head;
                now = temp;
                head = temp;
                continue;
            }
            now = now.next;
        }
        
        return head;
    }
}

2. 문제점

• 삽입 정렬을 사용했지만, O(N^2)의 시간 복잡도를 가지기 때문에 시간 초과가 발생 했다.

3. 실행 결과

 

2차 시도

1. 풀이 코드

class Solution {
    public ListNode sortList(ListNode head) {
        head = sort(head);
        return head;
    }

    static ListNode sort(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode start = head;
        ListNode slow = head;
        ListNode fast = head;

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

        ListNode mid = slow.next;
        slow.next = null;


        ListNode left = sort(start);
        ListNode right = sort(mid);
        return merge(left, right);
    }

    static ListNode merge(ListNode left, ListNode right) {
        ListNode mergeHead = new ListNode();
        ListNode lastNode = mergeHead;
        
        while(left != null && right != null) {
            if (left.val < right.val) {
                lastNode.next = left;
                lastNode = left;
                left = left.next;
            } else {
                lastNode.next = right;
                lastNode = right;
                right = right.next;
            }
        }
        
        while(left != null) {
            lastNode.next = left;
            lastNode = left;
            left = left.next;
        }

        while(right != null) {
            lastNode.next = right;
            lastNode = right;
            right = right.next;
        }
        return mergeHead.next;
    }
}

2. 1차 시도 코드 개선점

• 병합 정렬을 이용해 O(N log N)의 시간 복잡도로 문제를 해결했다.
• 두 개로 분리하고 정렬된 하나의 리스트로 병합하는 과정을 반복한다.

3. 실행 결과