Sort List - 리트코드

https://leetcode.com/problems/sort-list

평가

결과 : 성공?
풀이시간 : 2시간 30분

왜 이렇게 오래 걸렸냐, 문제의 요구사항 중 다음과 같은 내용이 있었다.
시간복잡도 NlogN, 공간복잡도 O(1)을 만족시켜보아라

해당 조건을 만족시키는 걸 도전했고 실패했다.
병합정렬을 사용하면 될 거라 생각했다.
연결리스트로 되어있어 어떻게 잘 만지면 새로운 노드를 만들지 않고 연결을 갈아끼울 수 있을 거라 생각했다.
그러나 수도코드에서도, 머리에서도 로직이 엉켜버려 실패했다.

결국 공간복잡도 요구사항을 포기하고, 병합정렬 로직을 생각하며 문제를 풀었고 성공했다.

고민을 정말 많이 했지만 만들지 못하였다. 그래서 정답을 보고 공간복잡도를 올려 볼 생각이다.

정답을 봐도 O(1) 시간복잡도를 만족하는 코드는 없다. 아,,, 내 시간,,,

아이디어

단순한 병합정렬입니다.
링크드리스트를 가운데를 기준으로 두 묶음으로 자릅니다.
두 묶음을 각각 정렬을 진행합니다.
투포인터 개념을 사용해 두 묶음을 하나의 묶음으로 묶습니다.

정답 코드

/**
 * 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) {
        ListNode next = head;

        // 총 원소 개수를 센다
        int totalCnt = 0;
        while(next != null) {
            next = next.next;
            totalCnt++;
        }
        // System.out.println(totalCnt);

        head = sort(head, totalCnt);
        return head;
    }

    // 정렬된 노드의 시작점을 반환한다
    public ListNode sort(ListNode head, int totalCnt) {
        if (totalCnt == 0) {
            return head;
        }
        if (totalCnt == 1) {
            head.next = null;
            return head;
        }

        // 가운데 값을 찾는다
        int idx = 0;
        ListNode middle = head;
        ListNode prev = null;
        while(idx < totalCnt/2) {
            prev = middle;
            middle = middle.next;
            idx++;
        }
        prev.next = null;
        
        ListNode second = sort(head, totalCnt/2);
        ListNode first = sort(middle,totalCnt - totalCnt/2);        

        ListNode answer = new ListNode(-1000000);
        ListNode start = answer;
        while(true) {
            if (first == null) {
                answer.next = second;
                break;
            }
            if (second == null) {
                answer.next = first;
                break;
            }

            if (first.val < second.val) {
                answer.next = new ListNode(first.val);
                answer = answer.next;
                first = first.next;
            } else {
                answer.next = new ListNode(second.val);
                answer = answer.next;
                second = second.next;
            }
        }

        return start.next;
    }
}