Merge Two Sorted Lists
No.21
You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.
Return the head of the merged linked list.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
r := &ListNode{0, nil}
head := r
for {
if list1 == nil {
r.Next = list2
break
}
if list2 == nil {
r.Next = list1
break
}
if list1.Val > list2.Val {
r.Next = list2
list2 = list2.Next
} else {
r.Next = list1
list1 = list1.Next
}
r = r.Next
}
return head.Next
}
|
Merge k Sorted Lists
No.23
You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.
Merge all the linked-lists into one sorted linked-list and return it.
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
|
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
r := &ListNode{0, nil}
head := r
for {
if list1 == nil {
r.Next = list2
break
}
if list2 == nil {
r.Next = list1
break
}
if list1.Val > list2.Val {
r.Next = list2
list2 = list2.Next
} else {
r.Next = list1
list1 = list1.Next
}
r = r.Next
}
return head.Next
}
func mergeKLists(lists []*ListNode) *ListNode {
len := len(lists)
if len == 0 {
return nil
}
if len == 1 {
return lists[0]
}
mid := len / 2
left := mergeKLists(lists[:mid])
right := mergeKLists(lists[mid:])
return mergeTwoLists(left, right)
}
|
分割链表
No.86
给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你应当 保留 两个分区中每个节点的初始相对位置
这个题读题就挺困惑，解题思路：根据x将链表拆分为两个链表，一个存储小于x的值，另一个存其它值，最后再将其合并即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| func partition(head *ListNode, x int) *ListNode {
big := &ListNode{0, nil}
less := &ListNode{0, nil}
th := head
nh := less
var temp *ListNode
for th != nil {
if th.Val >= x {
big.Next = th
big = big.Next
} else {
less.Next = th
less = less.Next
}
temp = th
th = th.Next
temp.Next = nil
}
less.Next = big.Next
return nh.Next
}
|