阅读更多
1 Question-21[★★]
Merge Two Sorted Lists
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
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
| public class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode pseudoHead = new ListNode(0);
ListNode iter = pseudoHead;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
iter.next = l1;
l1 = l1.next;
} else {
iter.next = l2;
l2 = l2.next;
}
iter = iter.next;
}
if (l1 != null) {
iter.next = l1;
}
if (l2 != null) {
iter.next = l2;
}
return pseudoHead.next;
}
}
|
2 Question-23[★★★★★]
Merge k Sorted Lists
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
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
|
public class Solution {
public ListNode mergeKLists(ListNode[] lists) {
Queue<ListNode> queue = new PriorityQueue<ListNode>(
new Comparator<ListNode>() {
@Override
public int compare(ListNode obj1, ListNode obj2) {
return obj1.val - obj2.val;
}
}
);
for (ListNode head : lists) {
if (head != null)
queue.offer(head);
}
ListNode pseudoHead = new ListNode(0);
ListNode iter = pseudoHead;
while (!queue.isEmpty()) {
ListNode top = queue.poll();
if (top.next != null) {
queue.offer(top.next);
}
iter.next = top;
iter = iter.next;
}
return pseudoHead.next;
}
}
|
3 Question-148[★★★★★]
Sort List
Sort a linked list in O(n log n) time using constant space complexity.
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
| public class Solution {
public ListNode sortList(ListNode head) {
ListNode pseudoHead = new ListNode(0);
pseudoHead.next = head;
mergeSort(pseudoHead, null);
return pseudoHead.next;
}
private void mergeSort(ListNode pseudoHead, ListNode tail) {
if (pseudoHead.next == tail || pseudoHead.next.next == tail) return;
ListNode slow = pseudoHead, fast = pseudoHead;
while (fast != tail && fast.next != tail) {
fast = fast.next.next;
slow = slow.next;
}
mergeSort(pseudoHead, slow.next);
mergeSort(slow, tail);
merge(pseudoHead, slow, tail);
}
private void merge(ListNode pseudoHead, ListNode mid, ListNode tail) {
ListNode midTail = mid.next;
ListNode iter1 = pseudoHead.next;
ListNode iter2 = mid.next;
ListNode iter = pseudoHead;
while (iter1 != midTail && iter2 != tail) {
if (iter1.val <= iter2.val) {
iter.next = iter1;
iter1 = iter1.next;
} else {
iter.next = iter2;
iter2 = iter2.next;
}
iter = iter.next;
}
while (iter1 != midTail) {
iter.next = iter1;
iter1 = iter1.next;
iter = iter.next;
}
while (iter2 != tail) {
iter.next = iter2;
iter2 = iter2.next;
iter = iter.next;
}
iter.next = tail;
}
}
|
