https://leetcode.com/problems/sort-list/?envType=study-plan-v2&envId=top-interview-150

148. Sort List

⭐ 문제

LinkedList의 head가 주어졌을 때, 이를 오름차순으로 정렬한 후의 List를 반환하세요

🤔 접근 방향

주어진 연결 리스트를 두 부분으로 분할하고, 각 부분을 재귀적으로 정렬한 다음, 두 정렬된 부분을 합병하여 하나의 정렬된 연결 리스트를 생성합니다. 이를 통해 연결 리스트의 모든 요소를 정렬된 순서로 재배치합니다.

✍️ 의사 코드

1. 만약 head가 null이거나 연결 리스트에 노드가 하나 이하라면, 그대로 head를 반환합니다.
2. 연결 리스트를 두 개의 서브 리스트로 분할하기 위해, slow와 fast라는 두 개의 포인터를 사용합니다. slow는 한 번에 한 칸씩, fast는 두 칸씩 이동합니다.
3. fast 포인터가 끝에 도달하면 slow 포인터는 중간 지점까지 이동합니다.
4. 중간 지점을 나타내는 mid 노드를 저장하고, slow 노드와 mid 노드 사이의 연결을 끊어 두 개의 서브 리스트로 분리합니다.
5. 두 개의 서브 리스트에 대해 재귀적으로 정렬을 수행합니다.
6. 두 개의 서브 리스트를 반복하면서 더 작은 값을 가진 노드를 tmp 노드 뒤에 연결합니다.
7. 병합된 리스트를 반환하기 위해 ref.next를 반환합니다.

✅ 나의 풀이

class Solution {
    public ListNode sortList(ListNode head) {
            // head가 노드이거나 연결 리스트 노드가 아닌 경우 head 반환, 연결리스트 노드만 처리
        if (head == null || head.next == null) {
            return head;
        }

        // slow는 이전 노드, fast는 다음 노드
        ListNode slow = head;
        ListNode fast = head.next;

        // slow 포인터는 한 칸씩 이동, fast 포인터는 두 칸씩 이동
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        // 중간 인덱스 저장
        ListNode mid = slow.next;
        // 노드 연결리스트 끊기
        slow.next = null;

        // 더 작은 연결 리스트로 계속해서 쪼개기
        ListNode left = sortList(head);
        ListNode right = sortList(mid);

        // 더미 노드 생성
        ListNode tmp = new ListNode(0);
        ListNode ref = tmp;

        // 왼쪽과 오른쪽 연결 리스트가 존재한다면
        while (left != null && right != null) {
            // 왼쪽 노드 값이 더 작다면
            if (left.val < right.val) {
                // 왼쪽 노드를 더미 노드 다음 노드에 연결
                tmp.next = left;
                // left 연결리스트는 다음 노드로 이동
                left = left.next;
            } else {
                // 오른쪽 노드를 더미 노드 다음 노드에 연결
                tmp.next = right;
                // right 연결리스트 다음 노드로 이동
                right = right.next;
            }
            // 더미 노드 오른쪽 이동
            tmp = tmp.next;
        }

        // 마지막으로 남은 노드는 가장 큰 노드이므로 가장 마지막에 더미 노드와 연결
        tmp.next = (left != null) ? left : right;

        // 더미 노드 다음 노드 (헤드 노드 반환)
        return ref.next;        
    }
}

🖥️ 결과

Runtime 0ms