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

合并两个有序链表（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…

算法数据结构 leetcode

本作品采用《CC 协议》，转载必须注明作者和本文链接

三斤

三斤和他的喵

课程读者 172 声望

一个PHPer的修行之路。欢迎大家关注我的公众号《三斤和他的喵》

1 人点赞

你将学到如 RESTFul 设计风格、PostMan 的使用、OAuth 流程，JWT 概念及使用和 API 开发相关的进阶知识。

从小程序个人账户申请开始，带你一步步进行开发一个微信小程序，直到提交微信控制台上线发布。

推荐文章：

更多推荐...

MySQL 8.0 官方手册翻译征集 10 / 14 |

面试 POPER 的后端开发工程师的离奇经历 40 / 105 |

博客

Laravel 实用小技巧 —— 如何快速更新 20 万条 MySQL 数据？ 20 / 26 |

分享创造

📙《高并发的哲学原理》开源图书发布十一天 star 数已经破千！ 49 / 17 |

博客

PHP面试高薪宝典系列: 常见基础算法（附完整代码） 25 / 3 |

博客

PHP实现汉诺塔算法 21 / 9 |

讨论数量: 1

Littlesqx

课程读者 255 声望 / 无业游民 @ __

/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val) { $this->val = $val; }
 * }
 */
class Solution 
{

    function mergeTwoLists($l1, $l2) 
    {
        $pointer = $root = new ListNode(-1);
        while ($l1 && $l2) {
            if ($l1->val <= $l2->val) {
                $pointer = $pointer->next = $l1;
                $l1 = $l1->next;
            } else {
                $pointer = $pointer->next = $l2;
                $l2 = $l2->next;
            }
        }
        $pointer->next = $l1 ?? $l2;

        return $root->next;
    }
}

6年前评论

captain2021

大佬从哪里学的这么高端的知识？

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容，与人为善，比聪明更重要！

帮助

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

合并两个有序链表（Merge-Two-Sorted-Lists）

解题思路

代码实现

GO语言实现

总结

推荐文章：

社区赞助商

关于 LearnKu

资源推荐

服务提供商

其他信息

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

合并两个有序链表（Merge-Two-Sorted-Lists）

解题思路

代码实现

GO语言实现

总结

推荐文章：

社区赞助商

关于 LearnKu

资源推荐

服务提供商

其他信息

请登录