Given the head of a linked list, return the list after sorting it in ascending order.
Follow up: Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?
Example 1:
Input: head = [4,2,1,3] Output: [1,2,3,4]
Example 2:
Input: head = [-1,5,3,4,0] Output: [-1,0,3,4,5]
Example 3:
Input: head = [] Output: []
Constraints:
- The number of nodes in the list is in the range
[0, 5 * 104]. -105 <= Node.val <= 105
排序链表。
题意是给你链表的头结点 head ，请将其按升序排列并返回排序后的链表，并满足时间O(nlogn)，空间O(1)的要求。
按照题目要求，因为时间是nlogn，所以思路只能是merge sort。
链表归并排序有几个问题要解决：
1、找链表的中间位置：
用快慢指针法，当快指针到达终点时，慢指针来到的位置就是中间位置
public ListNode getMiddle(ListNode head){
ListNode f=head;
ListNode s=head;
while(f.next!=null&&f.next.next!=null){
f=f.next.next;
s=s.next;
}
return s;
}
2、用中点位置，切分成左右两个链表，左右递归
ListNode middle=getMiddle(head);
ListNode next=middle.next;
middle.next=null;
ListNode l1=process(head);
ListNode l2=process(next);
3、写归并过程（同数组一样）
public ListNode mergeSort(ListNode l1,ListNode l2){
if(l1==null && l2==null){
return null;
}
ListNode dummy=new ListNode(0);
ListNode cur=dummy;
while(l1!=null && l2!=null){
if(l1.val<=l2.val){
cur.next=l1;
l1=l1.next;
cur=cur.next;
}else{
cur.next=l2;
l2=l2.next;
cur=cur.next;
}
}
if(l1!=null){
cur.next=l1;
}else{
cur.next=l2;
}
return dummy.next;
}
完整代码如下：
class Solution {
public ListNode sortList(ListNode head) {
return process(head);
}
public ListNode process(ListNode head){
if(head==null||head.next==null){
return head;
}
//find mid node
ListNode middle=getMiddle(head);
ListNode next=middle.next;
middle.next=null;
ListNode l1=process(head);
ListNode l2=process(next);
return mergeSort(l1,l2);
}
public ListNode getMiddle(ListNode head){
ListNode f=head;
ListNode s=head;
while(f.next!=null&&f.next.next!=null){
f=f.next.next;
s=s.next;
}
return s;
}
public ListNode mergeSort(ListNode l1,ListNode l2){
if(l1==null && l2==null){
return null;
}
ListNode dummy=new ListNode(0);
ListNode cur=dummy;
while(l1!=null && l2!=null){
if(l1.val<=l2.val){
cur.next=l1;
l1=l1.next;
cur=cur.next;
}else{
cur.next=l2;
l2=l2.next;
cur=cur.next;
}
}
if(l1!=null){
cur.next=l1;
}else{
cur.next=l2;
}
return dummy.next;
}
}