---
# System prepended metadata

title: '[148. Sort List](https://leetcode.com/problems/sort-list/)'
tags: [leetcode]

---

---
tags: leetcode
---

# [148. Sort List](https://leetcode.com/problems/sort-list/)
---
# My Solution
## Solution 1: Top-down Merge Sort
### The Key Idea for Solving This Coding Question
### C++ Code 1
```cpp=
/**
 * 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) {
        return mergeSort(head);
    }

private:
    ListNode *mergeSort(ListNode *head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }

        ListNode *fast = head, *slow = head, *preSlow = nullptr;
        while (fast != nullptr && fast->next != nullptr) {
            preSlow = slow;
            slow = slow->next;
            fast = fast->next->next;
        }


        ListNode *head2 = nullptr;
        if (fast != nullptr) {
            head2 = slow->next;
            slow->next = nullptr;
        } else {
            head2 = preSlow->next;
            preSlow->next = nullptr;
        }

        ListNode *left = mergeSort(head);
        ListNode *right = mergeSort(head2);

        return merge(left, right);
    }

    ListNode *merge(ListNode *list1, ListNode *list2) {
        ListNode *dummy = new ListNode(), *it = dummy;

        while (list1 != nullptr && list2 != nullptr) {
            if (list1->val < list2->val) {
                it->next = list1;
                list1 = list1->next;
            } else {
                it->next = list2;
                list2 = list2->next;
            }
            it = it->next;
        }

        if (list1 != nullptr) {
            it->next = list1;
        } else if (list2 != nullptr) {
            it->next = list2;
        }

        ListNode *sorted = dummy->next;
        delete dummy;
        return sorted;
    }
};
```
### Time Complexity
$O(nlogn)$
$n$ is the length of the linked list.
### Space Complexity
$O(logn)$
$n$ is the length of the linked list.
### C++ Code 2
```cpp=
/**
 * 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) {
        return mergeSort(head);
    }
    
private:
    ListNode *merge(ListNode *list1, ListNode *list2) {
        if (!list1) {
            return list2;
        }
        if (!list2) {
            return list1;
        }
        
        if (list1->val < list2->val) {
            list1->next = merge(list1->next, list2);
            return list1;
        }
        
        list2->next = merge(list1, list2->next);
        return list2;
    }

    ListNode *mergeSort(ListNode *head) {
        if (!head || !head->next) {
            return head;
        }
        
        ListNode *fast = head, *slow = head, *preSlow = nullptr;
        while (fast && fast->next) {
            preSlow = slow;
            slow = slow->next;
            fast = fast->next->next;
        }
        preSlow->next = nullptr;
        
        ListNode *head1 = mergeSort(head);
        ListNode *head2 = mergeSort(slow);
        ListNode *x = merge(head1, head2);
        
        return x;
    }
};
```
## Solution 2: Buttom-up Merge Sort
### The Key Idea for Solving This Coding Question
### C++ Code
```cpp=
/**
 * 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 *tail;
    ListNode *nextSubList;
    
    ListNode* sortList(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }
        
        int n = 0;
        for (ListNode *it = head; it != nullptr; it = it->next) {
            ++n;
        } // end of for-loop
        
        ListNode *start = head;
        ListNode dummyHead(0);
        for (int size = 1; size < n; size = size * 2) {
            tail = &dummyHead;
            while(start) {
                if (start->next == nullptr) {
                    tail->next = start;
                    break;
                }
                ListNode *mid = split(start, size);
                merge(start, mid);
                start = nextSubList;
            } // end of while-loop
            start = dummyHead.next;
        } // end of for loop
        
        return dummyHead.next;
    }
    
    ListNode* split(ListNode *start, int size) {
        ListNode *midPrev = start;
        ListNode *end = start->next;
        for (int index = 1; 
             index <size && (midPrev->next != nullptr || end->next != nullptr); 
             ++index) {
            if (end->next != nullptr) {
                if (end->next->next != nullptr) {
                    end = end->next->next;
                } else {
                    end = end->next;
                }
            }
            if (midPrev->next != nullptr) {
                midPrev = midPrev->next;
            }
        } // end of for-loop
        ListNode *mid = midPrev->next;
        nextSubList = end->next;
        midPrev->next = nullptr;
        end->next = nullptr;
        
        return mid;
    }
    
    void merge(ListNode *list1, ListNode *list2) {
        ListNode dummyHead(0);
        ListNode *newTail = &dummyHead;
        
        while(list1 != nullptr && list2 != nullptr) {
            if (list1->val < list2->val) {
                newTail->next = list1;
                list1 = list1->next;
            } else {
                newTail->next = list2;
                list2 = list2->next;
            }
            newTail = newTail->next;
        } // end of while-loop
        if (list1 != nullptr) {
            newTail->next = list1;
        } else {
            newTail->next = list2;
        }

        while (newTail->next != nullptr) {
            newTail = newTail->next;
        } // end of while
        
        tail->next = dummyHead.next;
        tail = newTail;
        
        return;
    }
};
```
### Time Complexity
$O(nlogn)$
$n$ is the length of the linked list.
### Space Complexity
$O(1)$
# Miscellaneous
<!--
# Test Cases
```
```
-->