本文介绍: Linked List 数据结构也在面试中经常出现,作为很好处理客户信息存储的结构很方便,也是重点必会项目之一,看看我们如何教懂白月光,成功邀约看电影吧。

21. 将两个有序列表融合

Linked List 数据结构也在面试中经常出现,作为很好处理客户信息存储的结构很方便,也是重点必会项目之一,看看我们如何教懂白月光,成功邀约看电影吧。

小白渣翻译

你将获得两个排序链表 list1 和 list2 的头。

将两个列表合并为一个排序列表。该列表应该通过将前两个列表的节点拼接在一起来形成。

返回合并链表的头。

例子

在这里插入图片描述

这里是小白理解

这种题目我们首先把他进行下条件梳理

  1. 链表类题目,我们首先要对链表结构有一定了。
  2. 题目描述意思说的简单一些,就是将两个有序链表的元素,最终都放在一个ListNode中,但是这里描述有些问题,他没有提到有序,如果加上,对于大家理解会更加清晰一些。

但是这题有些不清晰就在于得需要每个结果适合另外一个ListNode中的值有关系,而且相比于Array或者String要对ListNode List熟悉一些。,这时候黑长直女神过来问:小白,你这题怎么思考的啊?

小白内心镇定:小美,《年会不能停》有机会一起去看看吧?
在这里插入图片描述
哦,不是,这道题咱们可以考虑下用个dummy Node(虚拟节点)来辅助做题

  • 首先,我们为新的合并链表创建一个虚拟节点

  • 接下来我们创建两个指针,一个指向list1,另一个指向list2。

  • 现在遍历列表,直到其中一个列表耗尽为止。

  • 如果指向任一列表的节点的值小于另一个指针,则将该节点添加到我们的合并列表中并递增该指针。

小美:小伙子,可以啊,这不仅逻辑感人,阅读理解也有俩下子!不过电影票要你买单哦。

小白:没问题,谁叫为了“真爱”呢

在这里插入图片描述

真正面试环节

面试官:你可以解答这道”融合链表“的题目吗,来看看你对linked List结构的理解。

小白:嘿嘿,这不巧了么这不是
在这里插入图片描述

public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {

        // 首先,确保链表都不为空
        if (list1 != null && list2 != null) {

            // 如果链表1的第一个值小于链表2的第一个值
            if(list1.val < list2.val) {

                // 回归算法,找到链表1的next值
                list1.next = mergeTwoLists(list1.next, list2);
                return list1;
            } else {

                // 如果链表1的值大于链表2遍历的值
                list2.next = mergeTwoLists(list1, list2.next);
                return list2;
            }
        }

        // 如果链表1为空,那么直接返回链表2
        if(list1 == null) {
            return list2;
        }

        return list1;
    }

小明:OK,完事儿,等着面试官来表扬自己吧。他肯定会说:小子,你是个好手!工位都给你准备好了,工资你说了算。

面试官:矮油,不错啊,不过你这能不能写个测试啊。

小明OS:今年这个找工市场,人言洛阳花似锦,偏我来时不逢春。。。不是,怎么还让我些test case 啊!

static void printList(ListNode node) {
        while (node != null) {
            System.out.print(node.val + " ");
            node = node.next;
        }
    }

    public static void main(String[] args) {
        ListNode list1 = new ListNode(1);
        ListNode list2 = new ListNode(1);
        list1.next = new ListNode(2);
        list1.next.next = new ListNode(4);

        list2.next = new ListNode(3);
        list2.next.next = new ListNode(4);

        ListNode mergeTwoLists = mergeTwoLists(list1, list2);

        printList(mergeTwoLists);
    }

小白:您好,面试官,这回可以了吧,我终于有钱请小美看电影了!
在这里插入图片描述

============================================================================
🍀🍀🍀🍀🍀🍀更多算法题解请看 面试数据结构与算法总结分类+leetcode目录【基础版】
编码道路漫漫,只要先看脚下的路,徐徐前进即可。

原文地址:https://blog.csdn.net/u014739136/article/details/136024959

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。

如若转载,请注明出处:http://www.7code.cn/show_66653.html

如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除!

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注