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

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

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

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

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

返回合并链表的头。

在这里插入图片描述

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

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;
    }

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);
    }