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

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

本作品采用《CC 协议》,转载必须注明作者和本文链接
三斤
《L01 基础入门》
我们将带你从零开发一个项目并部署到线上,本课程教授 Web 开发中专业、实用的技能,如 Git 工作流、Laravel Mix 前端工作流等。
《G01 Go 实战入门》
从零开始带你一步步开发一个 Go 博客项目,让你在最短的时间内学会使用 Go 进行编码。项目结构很大程度上参考了 Laravel。
讨论数量: 1
/**
 * 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;
    }
}
3年前 评论
captain2021 3年前

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