题目要求
1
| Sort a linked list in O(n log n) time using constant space complexity.
|
用O(n log n)的时间复杂度和O(1)的空间复杂度检索一个链表。
思路和代码
在给出了明确的时间复杂度和空间复杂度后，我第一个想到的就是利用divide and conquer 方法进行排序。那么问题就归结为如何将链表分为大小相近的两半以及如何将二者合并。
了解利用分治法对数组进行排序的童鞋应该知道，我们会根据数组的下标将数组取一半分别进行排序后，再将排序好的二者进行合并。
那么将链表分为大小相近的两部分则需要我们用三个指针来进行。分别是prev, slow和fast，其中fast指针每次往前跑两步，slow往前跑一步，这样确保slow指针是第二部分开头的第一个指针，而prev则是slow指针的前一个指针。prev指针是用来折断链表的。
1
2
3
4
5
6
7
| ListNode prev = null, slow = head, fast = head;
while(fast!=null && fast.next!=null){
prev = slow;
slow = slow.next;
fast = fast.next.next;
}
prev.next = null;
|
之后再对折断的链表分别进行计算从而确保每一段内的元素为有序的。
之后我们需要将相邻的两段链表进行合并，这个就很简单了。只需要另设一个头指针，并每次比较两段的当前节点，取较小的节点加入头指针即可。
所有代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| public ListNode sortList(ListNode head) {
if(head == null || head.next == null) return head;
ListNode prev = null, slow = head, fast = head;
while(fast!=null && fast.next!=null){
prev = slow;
slow = slow.next;
fast = fast.next.next;
}
prev.next = null;
ListNode l1 = sortList(head);
ListNode l2 = sortList(slow);
return merge(l1, l2);
}
public ListNode merge(ListNode l1, ListNode l2){
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
while(l1!=null && l2!=null){
if(l1.val < l2.val){
ListNode tmp = l1.next;
cur.next = l1;
l1.next = null;
l1 = tmp;
}else{
ListNode tmp = l2.next;
cur.next = l2;
l2.next = null;
l2 = tmp;
}
cur = cur.next;
}
if(l1==null) cur.next = l2;
else cur.next = l1;
return dummy.next;
}
|