# Sort List
### Source
- leetcode: [Sort List | LeetCode OJ](https://leetcode.com/problems/sort-list/)
- lintcode: [(98) Sort List](http://www.lintcode.com/en/problem/sort-list/)
~~~
Sort a linked list in O(n log n) time using constant space complexity.
~~~
### 題解1 - 歸并排序(鏈表長度求中間節點)
鏈表的排序操作，對于常用的排序算法，能達到 O(nlogn)O(n \log n)O(nlogn)的復雜度有快速排序(平均情況)，歸并排序，堆排序。快速排序不一定能保證其時間復雜度一定滿足要求，歸并排序和堆排序都能滿足復雜度的要求。在數組排序中，歸并排序通常需要使用 O(n)O(n)O(n) 的額外空間，也有原地歸并的實現，代碼寫起來略微麻煩一點。但是對于鏈表這種非隨機訪問數據結構，所謂的「排序」不過是指針`next`值的變化而已，主要通過指針操作，故僅需要常數級別的額外空間，滿足題意。堆排序通常需要構建二叉樹，在這道題中不太適合。
既然確定使用歸并排序，我們就來思考歸并排序實現的幾個要素。
1. 按長度等分鏈表，歸并雖然不嚴格要求等分，但是等分能保證線性對數的時間復雜度。由于鏈表不能隨機訪問，故可以先對鏈表進行遍歷求得其長度。
1. 合并鏈表，細節已在 [Merge Two Sorted Lists | Data Structure and Algorithm](http://algorithm.yuanbin.me/zh-cn/linked_list/merge_two_sorted_lists.html) 中詳述。
在按長度等分鏈表時進行「后序歸并」——先求得左半部分鏈表的表頭，再求得右半部分鏈表的表頭，最后進行歸并操作。
由于遞歸等分鏈表的操作需要傳入鏈表長度信息，故需要另建一輔助函數。新鮮出爐的源碼如下。
~~~
/**
* Definition of ListNode
* class ListNode {
* public:
* int val;
* ListNode *next;
* ListNode(int val) {
* this->val = val;
* this->next = NULL;
* }
* }
*/
class Solution {
public:
/**
* @param head: The first node of linked list.
* @return: You should return the head of the sorted linked list,
using constant space complexity.
*/
ListNode *sortList(ListNode *head) {
if (NULL == head) {
return NULL;
}
// get the length of List
int len = 0;
ListNode *node = head;
while (NULL != node) {
node = node->next;
++len;
}
return sortListHelper(head, len);
}
private:
ListNode *sortListHelper(ListNode *head, const int length) {
if ((NULL == head) || (0 >= length)) {
return head;
}
ListNode *midNode = head;
int count = 1;
while (count < length / 2) {
midNode = midNode->next;
++count;
}
ListNode *rList = sortListHelper(midNode->next, length - length / 2);
midNode->next = NULL;
ListNode *lList = sortListHelper(head, length / 2);
return mergeList(lList, rList);
}
ListNode *mergeList(ListNode *l1, ListNode *l2) {
ListNode *dummy = new ListNode(0);
ListNode *lastNode = dummy;
while ((NULL != l1) && (NULL != l2)) {
if (l1->val < l2->val) {
lastNode->next = l1;
l1 = l1->next;
} else {
lastNode->next = l2;
l2 = l2->next;
}
lastNode = lastNode->next;
}
lastNode->next = (NULL != l1) ? l1 : l2;
return dummy->next;
}
};
~~~
### 源碼分析
1. 歸并子程序沒啥好說的了，見 [Merge Two Sorted Lists | Data Structure and Algorithm](http://algorithm.yuanbin.me/zh-cn/linked_list/merge_two_sorted_lists.html).
1. 在遞歸處理鏈表長度時，分析方法和 [Convert Sorted List to Binary Search Tree | Data Structure and Algorithm](http://algorithm.yuanbin.me/zh-cn/binary_search_tree/convert_sorted_list_to_binary_search_tree.html) 一致，**`count`表示遍歷到鏈表中間時表頭指針需要移動的節點數。**在紙上分析幾個簡單例子后即可確定，由于這個題需要的是「左右」而不是二叉搜索樹那道題需要三分——「左中右」，故將`count`初始化為1更為方便，左半部分鏈表長度為`length / 2`, 這兩個值的確定最好是先用紙筆分析再視情況取初值，不可死記硬背。
1. 找到中間節點后首先將其作為右半部分鏈表處理，然后將其`next`值置為`NULL`, 否則歸并子程序無法正確求解。這里需要注意的是`midNode`是左半部分的最后一個節點，`midNode->next`才是鏈表右半部分的起始節點。
1. 遞歸模型中**左、右、合并**三者的順序可以根據分治思想確定，即先找出左右鏈表，最后進行歸并(因為歸并排序的前提是兩個子鏈表各自有序)。
### 復雜度分析
遍歷求得鏈表長度，時間復雜度為 O(n)O(n)O(n), 「折半取中」過程中總共有 log(n)\log(n)log(n) 層，每層找中點需遍歷 n/2n/2n/2 個節點，故總的時間復雜度為 n/2?O(logn) n/2 \cdot O(\log n)n/2?O(logn) (折半取中), 每一層歸并排序的時間復雜度介于 O(n/2)O(n/2)O(n/2) 和 O(n)O(n)O(n)之間，故總的時間復雜度為 O(nlogn)O(n \log n)O(nlogn), 空間復雜度為常數級別，滿足題意。
### 題解2 - 歸并排序(快慢指針求中間節點)
除了遍歷鏈表求得總長外，還可使用看起來較為巧妙的技巧如「快慢指針」，快指針每次走兩步，慢指針每次走一步，最后慢指針所指的節點即為中間節點。使用這種特技的關鍵之處在于如何正確確定快慢指針的起始位置。
### C++
~~~
/**
* Definition of ListNode
* class ListNode {
* public:
* int val;
* ListNode *next;
* ListNode(int val) {
* this->val = val;
* this->next = NULL;
* }
* }
*/
class Solution {
public:
/**
* @param head: The first node of linked list.
* @return: You should return the head of the sorted linked list,
using constant space complexity.
*/
ListNode *sortList(ListNode *head) {
if (NULL == head || NULL == head->next) {
return head;
}
ListNode *midNode = findMiddle(head);
ListNode *rList = sortList(midNode->next);
midNode->next = NULL;
ListNode *lList = sortList(head);
return mergeList(lList, rList);
}
private:
ListNode *findMiddle(ListNode *head) {
if (NULL == head || NULL == head->next) {
return head;
}
ListNode *slow = head, *fast = head->next;
while(NULL != fast && NULL != fast->next) {
fast = fast->next->next;
slow = slow->next;
}
return slow;
}
ListNode *mergeList(ListNode *l1, ListNode *l2) {
ListNode *dummy = new ListNode(0);
ListNode *lastNode = dummy;
while ((NULL != l1) && (NULL != l2)) {
if (l1->val < l2->val) {
lastNode->next = l1;
l1 = l1->next;
} else {
lastNode->next = l2;
l2 = l2->next;
}
lastNode = lastNode->next;
}
lastNode->next = (NULL != l1) ? l1 : l2;
return dummy->next;
}
};
~~~
### 源碼分析
1. 異常處理不僅考慮了`head`, 還考慮了`head->next`, 可減少輔助程序中的異常處理。
1. 使用快慢指針求中間節點時，將`fast`初始化為`head->next`可有效避免無法分割兩個節點如`1->2->null`[fast_slow_pointer](#)。
- 求中點的子程序也可不做異常處理，但前提是主程序`sortList`中對`head->next`做了檢測。
1. 最后進行`merge`歸并排序。
****> 在遞歸和迭代程序中，需要尤其注意終止條件的確定，以及循環語句中變量的自增，以防出現死循環或訪問空指針。
### 復雜度分析
同上。
### Reference
- [Sort List | 九章算法](http://www.jiuzhang.com/solutions/sort-list/)
- fast_slow_pointer
> .
[LeetCode: Sort List 解題報告 - Yu's Garden - 博客園](http://www.cnblogs.com/yuzhangcmu/p/4131885.html)[ ?](# "Jump back to footnote [fast_slow_pointer] in the text.")
- Preface
- Part I - Basics
- Basics Data Structure
- String
- Linked List
- Binary Tree
- Huffman Compression
- Queue
- Heap
- Stack
- Set
- Map
- Graph
- Basics Sorting
- Bubble Sort
- Selection Sort
- Insertion Sort
- Merge Sort
- Quick Sort
- Heap Sort
- Bucket Sort
- Counting Sort
- Radix Sort
- Basics Algorithm
- Divide and Conquer
- Binary Search
- Math
- Greatest Common Divisor
- Prime
- Knapsack
- Probability
- Shuffle
- Basics Misc
- Bit Manipulation
- Part II - Coding
- String
- strStr
- Two Strings Are Anagrams
- Compare Strings
- Anagrams
- Longest Common Substring
- Rotate String
- Reverse Words in a String
- Valid Palindrome
- Longest Palindromic Substring
- Space Replacement
- Wildcard Matching
- Length of Last Word
- Count and Say
- Integer Array
- Remove Element
- Zero Sum Subarray
- Subarray Sum K
- Subarray Sum Closest
- Recover Rotated Sorted Array
- Product of Array Exclude Itself
- Partition Array
- First Missing Positive
- 2 Sum
- 3 Sum
- 3 Sum Closest
- Remove Duplicates from Sorted Array
- Remove Duplicates from Sorted Array II
- Merge Sorted Array
- Merge Sorted Array II
- Median
- Partition Array by Odd and Even
- Kth Largest Element
- Binary Search
- Binary Search
- Search Insert Position
- Search for a Range
- First Bad Version
- Search a 2D Matrix
- Search a 2D Matrix II
- Find Peak Element
- Search in Rotated Sorted Array
- Search in Rotated Sorted Array II
- Find Minimum in Rotated Sorted Array
- Find Minimum in Rotated Sorted Array II
- Median of two Sorted Arrays
- Sqrt x
- Wood Cut
- Math and Bit Manipulation
- Single Number
- Single Number II
- Single Number III
- O1 Check Power of 2
- Convert Integer A to Integer B
- Factorial Trailing Zeroes
- Unique Binary Search Trees
- Update Bits
- Fast Power
- Hash Function
- Count 1 in Binary
- Fibonacci
- A plus B Problem
- Print Numbers by Recursion
- Majority Number
- Majority Number II
- Majority Number III
- Digit Counts
- Ugly Number
- Plus One
- Linked List
- Remove Duplicates from Sorted List
- Remove Duplicates from Sorted List II
- Remove Duplicates from Unsorted List
- Partition List
- Two Lists Sum
- Two Lists Sum Advanced
- Remove Nth Node From End of List
- Linked List Cycle
- Linked List Cycle II
- Reverse Linked List
- Reverse Linked List II
- Merge Two Sorted Lists
- Merge k Sorted Lists
- Reorder List
- Copy List with Random Pointer
- Sort List
- Insertion Sort List
- Check if a singly linked list is palindrome
- Delete Node in the Middle of Singly Linked List
- Rotate List
- Swap Nodes in Pairs
- Remove Linked List Elements
- Binary Tree
- Binary Tree Preorder Traversal
- Binary Tree Inorder Traversal
- Binary Tree Postorder Traversal
- Binary Tree Level Order Traversal
- Binary Tree Level Order Traversal II
- Maximum Depth of Binary Tree
- Balanced Binary Tree
- Binary Tree Maximum Path Sum
- Lowest Common Ancestor
- Invert Binary Tree
- Diameter of a Binary Tree
- Construct Binary Tree from Preorder and Inorder Traversal
- Construct Binary Tree from Inorder and Postorder Traversal
- Subtree
- Binary Tree Zigzag Level Order Traversal
- Binary Tree Serialization
- Binary Search Tree
- Insert Node in a Binary Search Tree
- Validate Binary Search Tree
- Search Range in Binary Search Tree
- Convert Sorted Array to Binary Search Tree
- Convert Sorted List to Binary Search Tree
- Binary Search Tree Iterator
- Exhaustive Search
- Subsets
- Unique Subsets
- Permutations
- Unique Permutations
- Next Permutation
- Previous Permuation
- Unique Binary Search Trees II
- Permutation Index
- Permutation Index II
- Permutation Sequence
- Palindrome Partitioning
- Combinations
- Combination Sum
- Combination Sum II
- Minimum Depth of Binary Tree
- Word Search
- Dynamic Programming
- Triangle
- Backpack
- Backpack II
- Minimum Path Sum
- Unique Paths
- Unique Paths II
- Climbing Stairs
- Jump Game
- Word Break
- Longest Increasing Subsequence
- Palindrome Partitioning II
- Longest Common Subsequence
- Edit Distance
- Jump Game II
- Best Time to Buy and Sell Stock
- Best Time to Buy and Sell Stock II
- Best Time to Buy and Sell Stock III
- Best Time to Buy and Sell Stock IV
- Distinct Subsequences
- Interleaving String
- Maximum Subarray
- Maximum Subarray II
- Longest Increasing Continuous subsequence
- Longest Increasing Continuous subsequence II
- Graph
- Find the Connected Component in the Undirected Graph
- Route Between Two Nodes in Graph
- Topological Sorting
- Word Ladder
- Bipartial Graph Part I
- Data Structure
- Implement Queue by Two Stacks
- Min Stack
- Sliding Window Maximum
- Longest Words
- Heapify
- Problem Misc
- Nuts and Bolts Problem
- String to Integer
- Insert Interval
- Merge Intervals
- Minimum Subarray
- Matrix Zigzag Traversal
- Valid Sudoku
- Add Binary
- Reverse Integer
- Gray Code
- Find the Missing Number
- Minimum Window Substring
- Continuous Subarray Sum
- Continuous Subarray Sum II
- Longest Consecutive Sequence
- Part III - Contest
- Google APAC
- APAC 2015 Round B
- Problem A. Password Attacker
- Microsoft
- Microsoft 2015 April
- Problem A. Magic Box
- Problem B. Professor Q's Software
- Problem C. Islands Travel
- Problem D. Recruitment
- Microsoft 2015 April 2
- Problem A. Lucky Substrings
- Problem B. Numeric Keypad
- Problem C. Spring Outing
- Microsoft 2015 September 2
- Problem A. Farthest Point
- Appendix I Interview and Resume
- Interview
- Resume