让我们一起啃算法----合并两个有序链表

三斤和他的朋友们 · · 935 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

合并两个有序链表(Merge-Two-Sorted-Lists)

题干如下:

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 
示例:
  输入:1->2->4, 1->3->4
  输出:1->1->2->3->4->4
来源:力扣

这个题目和 两数相加 相似,都是考察对链表的操作。其实具体实现方式也差不多啦。

解题思路

根据题干我们知道,给定的两个链表是有序的。假设 l1 指向其中一个链表的头部,l2 指向另一个链表的头部,并初始化 headcurrent,使它们指向一个默认的节点。我们比较 l1 指向节点的值 V(l1)l2 指向节点的值 V(l2) 的大小,如果 V(l1) 的值小于 V(l2) 的值,则使 current.next 指向 l1 这个节点,current 指向下一个节点,l1 指向 l1的下一个节点,反之,则使 current.next 指向 l2 这个节点,current 指向下一个节点, l2 指向 l2的下一个节点

具体流程图如下:

注: l1l2 存在有一个指向 时的处理方案是:将 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...


有疑问加站长微信联系(非本文作者)

本文来自:Segmentfault

感谢作者:三斤和他的朋友们

查看原文:让我们一起啃算法----合并两个有序链表

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

935 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传