LeetCode148（排序链表）

发表于 | 分类于 ，

题目：

　　在O(nlogn)时间复杂度和常数级空间复杂度下，对链表进行排序。

思路：

　　时间复杂度为O(nlogn)，想到归并排序，但空间复杂度为常数级仍然存疑。

代码：

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
public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
			return head;
		}
        ListNode mid = getMid(head);
        ListNode right = mid.next;
        mid.next = null;
        return merge(sortList(head), sortList(right));
    }
	public ListNode getMid(ListNode head) {
		ListNode fastNode = head;
		ListNode slowNode = head;
		while(fastNode.next != null && fastNode.next.next != null) {
			fastNode = fastNode.next.next;
			slowNode = slowNode.next;
		}
		return slowNode;
	}
	public ListNode merge(ListNode head1,ListNode head2) {
		ListNode node1 = head1;
		ListNode node2 = head2;
		ListNode head;
		if (node1.val < node2.val) {
			head = node1;
			node1 = node1.next;
		}else {
			head = node2;
			node2 = node2.next;
		}
		ListNode node = head;
		while(node1 != null && node2 != null) {
			if (node1.val < node2.val) {
				node.next = node1;
				node1 = node1.next;
			}else {
				node.next = node2;
				node2 = node2.next;
			}
			node = node.next;
		}
		if (node1 != null) {
			node.next = node1;
		}
		if (node2 != null) {
			node.next = node2;
		}
		return head;
	}

复杂度分析及总结：

时间复杂度：
　　O(nlogn)。与数组的归并排序类似。
空间复杂度：
　　O(logn)。由于链表的归并排序不需要用到临时空间，故而起所需的空间仅仅为递归栈所消耗的空间。