[leetcode 148] Sort List

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

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

 

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 * 104].
• -105 <= Node.val <= 105

문제 풀이:

머지소트 사용

머지 소트를 다시 공부해야겠다!

eazymean.tistory.com/146

[알고리즘] 정렬 - Merge Sort

 

merge부분에서 ListNode fake를 만들지 않고 포인터만 만든다면 정렬이 되지 않는다.

ListNode* sorted = new ListNode(0); 하고 return sorted->next하면 결과값이 하나의 노드만 나온다...

직접 구현된 리스트노드가 없기 때문인거 같다. 실제 리스트 노드를 만들어주자.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if(!head || !head->next ){
            return head;
        }
        
        ListNode* mid = getMid(head);
        ListNode* left = sortList(head);
        ListNode* right = sortList(mid);
        
        return merge(left, right);
    }
    
    ListNode* merge(ListNode* l1, ListNode* l2){
        
        ListNode fake(0);
        ListNode* sorted = &fake;
        while(l1 && l2){
            if(l1->val < l2->val){
                sorted->next = l1;
                l1 = l1 ->next;
            }else {
                sorted->next = l2;
                l2 = l2->next;
            }
            sorted = sorted->next;
        }
        
        if(l1) sorted->next = l1;
        else sorted->next = l2;
        
        return fake.next;
    }
    
    ListNode* getMid(ListNode* head){
        ListNode* midPrev = nullptr;
        
        while(head && head->next){
            midPrev = (midPrev == nullptr)? head: midPrev->next;
            head = head->next->next;
        }
        ListNode* mid = midPrev->next;
        midPrev->next = nullptr;
        return mid;
    }
};