LeetCode(148)- Sort LIst(链表排序)

题目：

Sort a linked list in O(n log n) time using constant space complexity.

Example 1:

Input: 4->2->1->3 Output: 1->2->3->4 Example 2:

Input: -1->5->3->4->0 Output: -1->0->3->4->5

翻译：

使用常数空间，复杂度在O(n log n)时间内对链表进行排序。 示例1: 输入:4 - > 2 - > 1 - > 3 输出:1 - > 2 - > 3 - > 4 示例2: 输入:1 - > 5 - > 3 - > 4 - > 0 输出:1 - > 0 - > 3 - > 4 - > 5

思路：

因为题目要求时间复杂度为O(n log n),因此我们采用归并排序。 不了解归并排序请点击：归并排序原理

代码实现：

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode sortList(ListNode head) { if(head==null||head.next==null) return head; ListNode pre=head; ListNode slow=head; ListNode fast=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 a,ListNode b){ if(a==null) return b; if(b==null) return a; if(a.val<b.val){ a.next=merge(a.next,b); return a; }else{ b.next=merge(b.next,a); return b; } } } /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode sortList(ListNode head) { ListNode cur = head; int i = 0; while (cur != null) { cur = cur.next; i ++; } return sort(head, 0, i - 1); } public ListNode sort(ListNode head, int l, int r) { if (l >= r) { return head; } int mid = l + (r-l) / 2; ListNode cur = head; int i = 0; while (cur != null && i < mid - l) { cur = cur.next; i ++; } ListNode tmp = cur.next; cur.next = null; ListNode left = sort(head, l, mid); ListNode right = sort(tmp, mid + 1, r); ListNode merge = merge(left, right); return merge; } public ListNode merge(ListNode a, ListNode b) { ListNode dummyHead = new ListNode(0); ListNode cur = dummyHead; while (a != null || b != null) { if (a == null) { cur.next = b; break; } else if (b == null) { cur.next = a; break; } else if (a.val < b.val) { cur.next = new ListNode(a.val); cur = cur.next; a = a.next; } else { cur.next = new ListNode(b.val); cur = cur.next; b = b.next; } } return dummyHead.next; } }