蓝桥杯入门即劝退（十三）合并有序链表

分手后的思念是犯贱 2023-09-23 16:37 51阅读 0赞

**------持续更新蓝桥杯入门系列算法实例--------**

**如果你也喜欢Java和算法，欢迎订阅专栏共同学习交流！**

**你的点赞、关注、评论、是我创作的动力！**

**-------希望我的文章对你有所帮助--------**

**目录**

一、题目描述

二、代码实现

--------------------

## 一、题目描述 ##

将两个升序链表合并为一个新的 **升序** 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

**示例 1：**

![ac3caa733b3f1f5cef3e8e5b892953e2.jpeg][]

>     输入：l1 = [1,2,4], l2 = [1,3,4]
>     输出：[1,1,2,3,4,4]

**示例 2：**

>     输入：l1 = [], l2 = []
>     输出：[]

**示例 3：**

>     输入：l1 = [], l2 = [0]
>     输出：[0]

> **解题思路：1、已知两个链表均为升序链表，则想要将两个链表合并，必须一一比对两个链表的节点值。**
> 
> **2、新建一个虚拟节点，赋值给Pre节点，Pre指向list1的头节点。**
> 
> **3、比较两个链表头节点的值，则Pre指向更小的那个，并移动Pre。**
> 
> **4、链表遍历后，Pre指向后续节点，且如果最后有一个节点落单，则使得Pre指向最后一个节点，完成合并，返回虚拟节点的指针即结束。**

## 二、代码实现 ##

public  static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
            ListNode PreNode=new ListNode(-1);//虚拟节点
            ListNode pre=PreNode;
            while (list1!=null&&list2!=null){
                if (list1.val<=list2.val){//指向更小的头节点
                    pre.next=list1;
                    list1=list1.next;
                }
                else {
                    pre.next = list2;
                    list2=list2.next;
                }
                pre=pre.next;//移动Pre
            }
            pre.next=list1==null?list2:list1;//指向最后一个节点
            return PreNode.next;
        }

**感谢爱学习的你看到了最后，点个关注、赞支持一下吧！**

[ac3caa733b3f1f5cef3e8e5b892953e2.jpeg]: https://img-blog.csdnimg.cn/img_convert/ac3caa733b3f1f5cef3e8e5b892953e2.jpeg