148. Sort List
文章目录
Sort a linked list in
O(n log n)time using constant space complexity.
题目分析
一看到sort问题,而且时间复杂度要求又是O(n log n),很自然地就会想到Merge sort. Merge sort数组时,pseudo code如下:
func mergesort( var a as array ) if ( n == 1 ) return a var l1 as array = a[0] ... a[n/2] var l2 as array = a[n/2+1] ... a[n] l1 = mergesort( l1 ) l2 = mergesort( l2 ) return merge( l1, l2 ) end func func merge( var a as array, var b as array ) var c as array while ( a and b have elements ) if ( a[0] > b[0] ) add b[0] to the end of c remove b[0] from b else add a[0] to the end of c remove a[0] from a while ( a has elements ) add a[0] to the end of c remove a[0] from a while ( b has elements ) add b[0] to the end of c remove b[0] from b return c end func(Reference: http://www.algorithmist.com/i... )
这道题要求是sort linked list,所以在上面pseudo code的基础上还要进行一些额外操作:
-
找到List的中点,使用快慢指针法。
ListNode slow = head; ListNode fast = head; while (fast.next != null && fast.next.next != null) { slow = slow.next; fast = fast.next.next; }需要注意的是,找到中点后要把链表分成两段,即:
slow.next = null; Merge两个链表。这部分代码应该近似于merge 2 sorted lists这道题的答案。
代码
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
// find the mid point of the linked list
ListNode slow = head;
ListNode fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode head2 = slow.next;
slow.next = null;
// if there's only 1 element in the list, continue splitting
ListNode list1 = null;
ListNode list2 = null;
if (head != head2) {
list1 = sortList(head);
list2 = sortList(head2);
}
// merge 2 lists
return mergeList(list1, list2);
}
// merge 2 lists. reference: Merge 2 Linked List
public ListNode mergeList(ListNode head1, ListNode head2) {
if (head1 == null) {
return head2;
}
if (head2 == null) {
return head1;
}
ListNode dummy = new ListNode(0);
ListNode p = dummy;
while (head1 != null && head2 != null) {
if (head1.val <= head2.val) {
p.next = head1;
p = p.next;
head1 = head1.next;
} else {
p.next = head2;
p = p.next;
head2 = head2.next;
}
}
if (head1 != null) {
p.next = head1;
}
if (head2 != null) {
p.next = head2;
}
return dummy.next;
}
}
复杂度分析
时间复杂度 O(n log n)
空间复杂度 O(1)
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论