小白水平理解面试经典题目LeetCode 21. Merge Two Sorted Lists【Linked List类】

21. 将两个有序列表融合

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

小白渣翻译

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

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

返回合并链表的头。

例子

在这里插入图片描述

这里是小白理解

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

链表类题目，我们首先要对链表结构有一定了。
题目描述意思说的简单一些，就是将两个有序链表的元素，最终都放在一个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);
    }