合并两个有序链表(Merge-Two-Sorted-Lists)
题干如下:
将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例:
输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4
来源:力扣
这个题目和 两数相加 相似,都是考察对链表的操作。其实具体实现方式也差不多啦。
解题思路
根据题干我们知道,给定的两个链表是有序的。假设 l1 指向其中一个链表的头部,l2 指向另一个链表的头部,并初始化 head 和 current,使它们指向一个默认的节点。我们比较 l1 指向节点的值 V(l1) 与 l2 指向节点的值 V(l2) 的大小,如果 V(l1) 的值小于 V(l2) 的值,则使 current.next 指向 l1 这个节点,current 指向下一个节点,l1 指向 l1的下一个节点,反之,则使 current.next 指向 l2 这个节点,current 指向下一个节点, l2 指向 l2的下一个节点。
具体流程图如下:
注: l1 和 l2 存在有一个指向 空 时的处理方案是:将 current.next 指向不是空的的链表即可,因为给定的两个链表本身是有序的。
代码实现
GO语言实现
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
var (
head = &ListNode{}
current = head
)
for true {
// l1 为空时,将 current.next 指向 l2 即可
if l1 == nil {
current.Next = l2
break
}
// l2 为空时,将 current.next 指向 l1 即可
if l2 == nil {
current.Next = l1
break
}
// 如果 l1的值 小于 l2的值 current.next指向l1,l1后移
if l1.Val < l2.Val {
current.Next = l1
l1 = l1.Next
} else {
// 如果 l2的值 小于等于 l1的值 current.next指向l2,l2后移
current.Next = l2
l2 = l2.Next
}
// current 后移一位
current = current.Next
}
// head 指向的是默认的节点,head.next 才是结果链表的头节点
return head.Next
}
总结
每天进步一点点,加油!
算法教程项目,每天更新一题,点个 star 支持一下呀:
https://github.com/wx-satellite/learning-a...
有疑问加站长微信联系(非本文作者)