p148

发表于 | 分类于 |

LeetCode 148 Sort List 题解

1.题目：

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

题意：

给一个链表排序，控制时间复杂度

2.解题思路:

使用三向快排，代码已注释
踩的坑：
Line 44: java.lang.StackOverflowError
使用归并排序时递归太深了，报错。（代码也附上）
看到测试数据有很多重复的值选择三向快排进行排序

3.代码

[title] [] [url] [link text]
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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
 

package leetcode;

import tool.ListNode;

public class p148 {
	public static void main(String[] args) {
		int[] nums = { 1, 1, 2 };
		ListNode a = new ListNode(1);
		ListNode a2 = new ListNode(3);
		ListNode a3 = new ListNode(2);
		ListNode a4 = new ListNode(2);
		ListNode a5 = new ListNode(3);
		a.next = a2;
		a2.next = a3;

		a4.next = a5;
		a = sortList(a);
		while (a != null) {
			System.out.println(a.val);
			a = a.next;
		}

	}

	public static ListNode sortList(ListNode head) {
		if (head == null || head.next == null) {
			return head;
		}

		ListNode prev = head;
		ListNode head1 = new ListNode(0);
		ListNode head2 = new ListNode(0);
		ListNode h1 = head1;
		ListNode h2 = head2;
		ListNode node = head.next;
		while (node != null) {
			if (node.val < head.val) {
				h1.next = node;
				h1 = h1.next;
			} else if (node.val > head.val) {
				h2.next = node;
				h2 = h2.next;
			} else {
				prev.next = node;
				prev = prev.next;
			}
			node = node.next;
		}

		h1.next = null;
		h2.next = null;
		prev.next = null;
		head1.next = sortList(head1.next);
		head2.next = sortList(head2.next);
		h1 = head1;// 前半段
		while (h1.next != null) {
			h1 = h1.next;
		}

		h1.next = head;// prev操作之后的中间段 pre为head的结尾 head的头部为用来分隔的中介数
		prev.next = head2.next;// 连接这三段
		return head1.next;

		// 归并排序

		// while (ListNode2.next != null && ListNode2.next.next != null) {
		//
		// ListNode1 = ListNode1.next;
		// ListNode2 = ListNode2.next.next;// 将链表平分，跳出循环l2走到了尽头,L1只走了一半。
		//
		// }
		//
		// ListNode n1 = sortList(ListNode1.next);// 排序head后半段
		// ListNode1.next = null;// 截取head前半段
		// ListNode n2 = sortList(head);
		// return merge(n1, n2);
	}
	//
	// // 合并两个有序的链表
	// public static ListNode merge(ListNode l1, ListNode l2) {
	//
	// if (l1 == null)
	// return l2;
	// if (l2 == null)
	// return l1;
	//
	// if (l1.val < l2.val) {
	// l1.next = merge(l1.next, l2);
	// return l1;
	// } else {
	// l2.next = merge(l2.next, l1);
	// return l2;
	// }
	//
	// }
}

4.一些总结：