Sort a linked list in O(n log n) time using constant space complexity.
Example 1:
Input: 4->2->1->3Output: 1->2->3->4
Example 2:
Input: -1->5->3->4->0Output: -1->0->3->4->5
给一个链表排序，要求Time: O(nlogn), constant space complexity.
解法：1. 把链表从中间分开Break the list to two in the middle. 2. 递归排序两个子链表Recursively sort the two sub lists. 3. 合并子链表Merge the two sub lists.
解法：归并排序。由于有时间和空间复杂度的要求。把链表从中间分开，递归下去，都最后两个node时开始合并，返回上一层继续合并，直到结束。找中间点的方法可以用快慢指针，快指针走2步，慢指针走1步。也可以求出链表长度，再分开链表
Java:
public class Solution { public ListNode sortList(ListNode head) { if (head == null || head.next == null) return head; ListNode slow = head, fast = head, pre = head; while (fast != null && fast.next != null) { pre = slow; slow = slow.next; fast = fast.next.next; } pre.next = null; return merge(sortList(head), sortList(slow)); } public ListNode merge(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(-1); ListNode cur = dummy; while (l1 != null && l2 != null) { if (l1.val < l2.val) { cur.next = l1; l1 = l1.next; } else { cur.next = l2; l2 = l2.next; } cur = cur.next; } if (l1 != null) cur.next = l1; if (l2 != null) cur.next = l2; return dummy.next; }} Java:
public class Solution { public ListNode sortList(ListNode head) { if (head == null || head.next == null) return head; ListNode slow = head, fast = head, pre = head; while (fast != null && fast.next != null) { pre = slow; slow = slow.next; fast = fast.next.next; } pre.next = null; return merge(sortList(head), sortList(slow)); } public ListNode merge(ListNode l1, ListNode l2) { if (l1 == null) return l2; if (l2 == null) return l1; if (l1.val < l2.val) { l1.next = merge(l1.next, l2); return l1; } else { l2.next = merge(l1, l2.next); return l2; } }} Python:
class ListNode: def __init__(self, x): self.val = x self.next = None def __repr__(self): if self: return "{} -> {}".format(self.val, repr(self.next))class Solution: # @param head, a ListNode # @return a ListNode def sortList(self, head): if head == None or head.next == None: return head fast, slow, prev = head, head, None while fast != None and fast.next != None: prev, fast, slow = slow, fast.next.next, slow.next prev.next = None sorted_l1 = self.sortList(head) sorted_l2 = self.sortList(slow) return self.mergeTwoLists(sorted_l1, sorted_l2) def mergeTwoLists(self, l1, l2): dummy = ListNode(0) cur = dummy while l1 != None and l2 != None: if l1.val <= l2.val: cur.next, cur, l1 = l1, l1, l1.next else: cur.next, cur, l2 = l2, l2, l2.next if l1 != None: cur.next = l1 if l2 != None: cur.next = l2 return dummy.nextif __name__ == "__main__": head = ListNode(3) head.next = ListNode(4) head.next.next = ListNode(1) head.next.next.next= ListNode(2) print(Solution().sortList(head)) C++:
class Solution {public: ListNode* sortList(ListNode* head) { if (!head || !head->next) return head; ListNode *slow = head, *fast = head, *pre = head; while (fast && fast->next) { pre = slow; slow = slow->next; fast = fast->next->next; } pre->next = NULL; return merge(sortList(head), sortList(slow)); } ListNode* merge(ListNode* l1, ListNode* l2) { ListNode *dummy = new ListNode(-1); ListNode *cur = dummy; while (l1 && l2) { if (l1->val < l2->val) { cur->next = l1; l1 = l1->next; } else { cur->next = l2; l2 = l2->next; } cur = cur->next; } if (l1) cur->next = l1; if (l2) cur->next = l2; return dummy->next; }}; C++:
class Solution {public: ListNode* sortList(ListNode* head) { if (!head || !head->next) return head; ListNode *slow = head, *fast = head, *pre = head; while (fast && fast->next) { pre = slow; slow = slow->next; fast = fast->next->next; } pre->next = NULL; return merge(sortList(head), sortList(slow)); } ListNode* merge(ListNode* l1, ListNode* l2) { if (!l1) return l2; if (!l2) return l1; if (l1->val < l2->val) { l1->next = merge(l1->next, l2); return l1; } else { l2->next = merge(l1, l2->next); return l2; } }};