题目
将两个升序链表合并为一个新的升序链表并返回。
示例:
输入:l1 = [1,2,4], l2 = [1,3,4]
输出:[1,1,2,3,4,4]
分析
比较大小
那必须两个链表都要遍历,无论从哪个链表开始遍历,都不影响,假设我们从l1开始遍历,取出第一个数比较,只有两种情况,小于等于或大于,那么意味着我们这一轮比较我们获得了其中的较小值。
那么这个最小值是否是我们目标的链表的最小值呢?
答案,是的!假设l1第一个数v1比另一个链表l2的第一个值v2小,那必然比l2整个链表小,因为链表是升序的,同时v1也是l1中最小的值,那问题就比较简单了,我们只需要取出这个最小节点,放到一个新节点末尾,那么不就可以得到我们的目标链表了吗?于是就有以下实现:
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
// 定义目标链表
var l3 = &ListNode{0, nil}
// 由于新节点需要放到链表末尾,所以在这个过程中我们需要更新目标链表尾节点。
tail := l3
// 当其中一个链表为空时结束
for l1 != nil && l2 != nil {
v1 := l1.Val
v2 := l2.Val
// 每一轮,总是将最小的值放到l3末尾,同时剔除该节点
if v1 <= v2 {
tail.Next = &ListNode{v1, nil}
p := l1.Next
l1 = p
} else {
tail.Next = &ListNode{v2, nil}
p := l2.Next
l2 = p
}
tail = tail.Next
}
return l3.Next
}
提交测试,
1/208 cases passed (N/A)
Testcase
[1,2,4]
[1,3,4]
Answer
[1,1,2,3,4]
Expected Answer
[1,1,2,3,4,4]
不通过,仔细查看,原来是漏掉了节点。
再查看代码,由于剔除节点后,链表长度会不一致,那整个遍历会导致其中一个链表先为空,那么至于是哪个链表为空,我们无需关心,只需要将不为空的链表放到目标链表末尾即可。完整实现如下:
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
// 定义目标链表(哑节点)
var l3 = &ListNode{0, nil}
// 由于新节点需要放到链表末尾,所以在这个过程中我们需要更新目标链表尾节点。
tail := l3
// 当其中一个链表为空时结束
for l1 != nil && l2 != nil {
v1 := l1.Val
v2 := l2.Val
// 每一轮,总是将最小的值放到l3末尾,同时剔除该节点
if v1 <= v2 {
tail.Next = &ListNode{v1, nil}
p := l1.Next
l1 = p
} else {
tail.Next = &ListNode{v2, nil}
p := l2.Next
l2 = p
}
tail = tail.Next
}
// 将不为空的链表放到目标链表末尾
if l1 != nil {
tail.Next = l1
}
if l2 != nil {
tail.Next = l2
}
return l3.Next
}
提交测试,完美通过。
208/208 cases passed (0 ms)
Your runtime beats 100 % of golang submissions
Your memory usage beats 10.18 % of golang submissions (2.6 MB)