Sort a linked list in O(n log n) time using constant space complexity.
方法1优化后：
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode sortList(ListNode head) { if (head == null || head.next == null) { return head; } //平分结点，分成两个分段 ListNode pre = null, slow = head, fast = head; while (fast != null && fast.next != null) {//如果是奇数个结点，多出来的一个结点放在了后面的部分 pre = slow;//需要保留slow的上一个节点 slow = slow.next; fast = fast.next.next; } pre.next = null;//把链表断开，分成2段；pre指向上一段的最后一个节点；sl ow指向下一段的第一个节点； //每个分支都要排序，然后按序合并 ListNode l1 = sortList(head);//head->pre ListNode l2 = sortList(slow);//slow->end //按序合并，子分支和大分支都在这里合并 return merge(l1, l2); }//sortList /** * 优化后，不对.val赋值，比上一个版本简洁 * * @param l1 * @param l2 * @return */ public ListNode merge(ListNode l1, ListNode l2) { ListNode res = new ListNode(0), p = res; while (l1 != null && l2 != null) { if (l1.val < l2.val) { p.next = l1; //p = p.next;//正确 p = l1;//正确 l1 = l1.next;//此处l1 = l1.next不会导致p指向的地址变化 //System.out.println("l1:" + l1); } else { p.next = l2; //p = p.next;//正确 p = l2;//正确 l2 = l2.next;//此处l2 = l2.next不会导致p指向的地址变化 //System.out.println("l2:" + l2); } //p = p.next;//正确,while中不写p = p.next时，在while外需要写这一句 //System.out.println("p:" + p); //System.out.println("res:" + res);//p指向的地址变化，不会导致res指向的地址变化 //System.out.println("---------"); }//while if (l1 != null) { //这样才完美 p.next = l1; } if (l2 != null) { p.next = l2; } // if (l2 == null) { //这样正确，但不够完美 // p.next = l1; // } // if (l1== null) { // p.next = l2; // } return res.next;// ListNode res = new ListNode(0)因为第一个结点是0，所以这里是 res.next,而不是res }//merge //https://programskills.blog.csdn.net/article/details/76793696 public static void main(String[] args) { ListNode A = new ListNode(6); A.next = new ListNode(2); A.next.next = new ListNode(4); A.next.next.next = new ListNode(3); A.next.next.next.next = new ListNode(5); LeetCode_148_SortList main = new LeetCode_148_SortList(); ListNode C = main.sortList(A); System.out.println(C); } }Runtime: 9 ms, faster than 24.24% of Java online submissions for Sort List.
Memory Usage: 53.5 MB, less than 5.07% of Java online submissions for Sort List.
l2:null p:ListNode@266474c2 res:ListNode@6f94fa3e --------- l1:null p:ListNode@5e481248 res:ListNode@66d3c617 --------- l2:ListNode@63947c6b p:ListNode@5e481248 res:ListNode@2b193f2d --------- l1:null p:ListNode@355da254 res:ListNode@2b193f2d --------- l1:ListNode@4dc63996 p:ListNode@266474c2 res:ListNode@d716361 //最后一次merge --------- l2:ListNode@355da254 p:ListNode@5e481248 res:ListNode@d716361 --------- l2:ListNode@63947c6b p:ListNode@355da254 res:ListNode@d716361 --------- l2:null p:ListNode@63947c6b res:ListNode@d716361 --------- ListNode@266474c2解析：
For the linked list = [10,1,60,30,5], the following figure illustrates the merge sort process using a top down approach.
Complexity Analysis
Time Complexity: \mathcal{O}(n \log n)O(nlogn), where nn is the number of nodes in linked list. The algorithm can be split into 2 phases, Split and Merge.Let's assume that nn is power of 22. For n = 16, the split and merge operation in Top Down fashion can be visualized as follows
https://leetcode.com/problems/sort-list/solution/
时间复杂度：16个节点分别要merge4次（一个节点与另一个节点合并成2个，每2个节点merge成4个，每4个节点merge成8个，每8个节点merge成16个）
空间复杂度：递归树的最大深度。计算阶段，每一段子链表的头节点都会保存在栈中。
方法1未优化：
package com.main; class ListNode { int val; ListNode next; ListNode(int x) { val = x; } } public class Main { public ListNode sortList(ListNode head) { if (head == null || head.next == null) { return head; } //平分结点，分成两个分支 ListNode cur = null, slow = head, fast = head; while (fast != null && fast.next != null) {//如果是奇数个结点，多出来的一个结点放在了后面的部分 cur = slow; slow = slow.next; fast = fast.next.next; } cur.next = null; //每个分支都要排序，然后按序合并 ListNode l1 = sortList(head); ListNode l2 = sortList(slow); //按序合并，子分支和大分支都在这里合并 return merge(l1, l2); }//sortList public ListNode merge(ListNode l1, ListNode l2) { ListNode res = new ListNode(0), p = res; while (l1 != null && l2 != null) { if (l1.val < l2.val) { res.val = l1.val; p.next = l1;//这一句别忘了 l1 = l1.next; } else { res.val = l2.val; p.next = l2; l2 = l2.next; } p = p.next; }//while if (l1 != null) { p.next = l1; } if (l2 != null) { // p.next = l2.next;不能是p.next = l2.next p.next = l2; } return res.next;// ListNode res = new ListNode(0)因为第一个结点是0，所以这里是 res.next,而不是res }//merge public static void main(String[] args) { ListNode A = new ListNode(6); A.next = new ListNode(2); A.next.next = new ListNode(4); A.next.next.next = new ListNode(3); A.next.next.next.next = new ListNode(5); Main main = new Main(); ListNode C = main.sortList(A); System.out.println(C); } }
以下为递归执行流程，分别是2个结点和4个结点的情况
15 / 15 test cases passed. Status: Accepted Runtime: 8 ms T(n) = O(nlogn)
