Leetcode - 148. Sort List

문제

주어진 링크드 리스트를 오름차순 정렬하라.

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

해결 O(nlogn) / O(n)

각 노드를 heap에 넣고 하나씩 pop하면서 새로 링크르 리스트를 생성.

• 기존 노드를 재조합해서 새 링크드 리스트를 생성할때는 마지막 노드부터 시작해서 head로 만들어야함. 아래 코드 참고

        while (!pq.empty() ) {
            node = pq.top();
            node->next = newhead;
            newhead = node;
            pq.pop();
        }

• 따라서 heap은 max heap이어야함. 큰 값의 노드부터 링크의 마지막에 생성되니.

class myCompare {
public:
    bool operator() (const ListNode *p1, const ListNode *p2) {
        return p1->val < p2->val;
    }
};

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        priority_queue<ListNode*, vector<ListNode*>, myCompare> pq;
        ListNode *node = head;
        while (node != NULL) {
            pq.push(node);
            node = node->next;
        }
        ListNode *newhead = NULL;
        while (!pq.empty() ) {
            node = pq.top();
            node->next = newhead;
            newhead = node;
            pq.pop();
        }
        return newhead;
    }
};

해결 - merge sort방법 O(nlogn)

Divide and Conquer 전략으로 푸는 방법.
중간노드를 찾아 두개의 리스트로 나눈뒤 각각 정렬하고 그 두개를 다시 합치면서 정렬.
return merge_list(sortList(head), sortList(r_head));

class Solution {
    ListNode *merge_list(ListNode *left, ListNode *right) {
        ListNode *newhead = new ListNode;
        ListNode *prev = newhead;
        
        while (left && right) {
            if (left->val < right->val) {
                prev->next = left;
                left = left->next;
            } else {
                prev->next = right;
                right = right->next;
            }
            prev = prev->next;
        }
        prev->next = (left) ? left : right; // node is not null
        return newhead->next;
    }
public:
    ListNode *sortList(ListNode *head) {
        if (!head || !head->next)
            return head;
        ListNode *r_head = head;
        ListNode *slow = head;
        ListNode *fast = head;
        
        while (fast->next && fast->next->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        r_head = slow->next;
        slow->next = NULL;
        
        return merge_list(sortList(head), sortList(r_head));
    }
};