Sort List
Sort a linked list in O(n log n) time using constant space complexity.
Merge sort
先根据mid node把list 分割为 单个 node ,然后merge
/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode sortList(ListNode head) { if(head == null || head.next == null) return head; ListNode fast = head.next.next; ListNode p = head;
// while结束时 p指向的是中点的前一个节点 while(fast != null && fast.next != null){ p = p.next; fast = fast.next.next; } // p is the mid node of the list // 这两行代码顺序不能换 ListNode h2 = sortList(p.next); p.next = null; // 把前半部分的merge sort结果 和后半部分的merge sort结果再merge sort return mergeSort(sortList(head), h2); } // merge two sorted list private ListNode mergeSort(ListNode h1, ListNode h2){ ListNode fakeNode = new ListNode(Integer.MIN_VALUE); ListNode runner = fakeNode; while(h1 != null && h2 != null){ if(h1.val < h2.val){ runner.next = h1; h1 = h1.next; }else{ runner.next = h2; h2 = h2.next; } runner = runner.next; } if(h1 != null){ runner.next = h1; } if(h2 != null){ runner.next = h2; } return fakeNode.next; } }