LeetCode-Sort List

Sort List

##题目

####Sort List

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

##解题思路
该题是对链表进行排序，但是在时间复杂度上要求是O(nlogn),也就是说排序的方法只可能是归并排序和快速排序，由于前面我们已经做过两个有序链表的合并操作Merge Two Sorted Lists.因此这里我们可以使用归并排序进行处理。

需要注意的是，其中链表之间的链接操作和跳转需要比较小心的处理。

##算法代码
代码采用JAVA实现：

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
/**
 * 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) {
        return mergeSort(head);
    }

    //归并排序
	public ListNode mergeSort(ListNode head)
	{
		if(head==null || head.next==null)
			return head;
		//找到中间节点，可以定义两个指针，一个每次1步向后前进，一个每次2步向后前进，快的到达末尾后，慢的正好在中间。
		ListNode worker=head;
		ListNode runner=head;
		while(runner.next!=null && runner.next.next!=null)
		{
			worker=worker.next;
			runner=runner.next.next;
		}

		ListNode newhead=worker.next;
		worker.next=null;
		//递归排序两个链表
		ListNode head1=mergeSort(head);
		ListNode head2=mergeSort(newhead);
		return merge(head1,head2); //合并两个有序链表
	}    

	public ListNode merge(ListNode head1,ListNode head2)
	{
		if(head1==null)
			return head2;
		if(head2==null)
			return head1;
		ListNode p=head1;
		ListNode q=head2;
		ListNode newhead=new ListNode(0);
		ListNode r=newhead;
		while(p!=null && q!=null)
		{
			if(p.val<q.val)
			{
				r.next=p;
				p=p.next;
				r=r.next;
			}else{
				r.next=q;
				q=q.next;
				r=r.next;
			}
		}
		while(p!=null)
		{
			r.next=p;
			p=p.next;
			r=r.next;
		}

		while(q!=null)
		{
			r.next=q;
			q=q.next;
			r=r.next;
		}

		return newhead.next;
	}
}

Comments

▲