【Java版oj】合并两个有序链表

àì夳堔傛蜴生んèń 2024-04-01 09:03 162阅读 0赞

**目录**

一、原题再现

二、问题分析

三、完整代码

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

> ## 一、原题再现 ##
> 
> [21. 合并两个有序链表][21.]
> 
> 难度简单
> 
> 将两个升序链表合并为一个新的 **升序** 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
> 
> **示例 1：**
> 
> ![fcbf72d9c72e3cf739efe539b76f397c.jpeg][]
> 
>     输入：l1 = [1,2,4], l2 = [1,3,4]
>     输出：[1,1,2,3,4,4]
> 
> **示例 2：**
> 
>     输入：l1 = [], l2 = []
>     输出：[]
> 
> **示例 3：**
> 
>     输入：l1 = [], l2 = [0]
>     输出：[0]
> 
> **提示：**
> 
>  *  两个链表的节点数目范围是 `[0, 50]`
>  *  `-100 <= Node.val <= 100`
>  *  `l1` 和 `l2` 均按 **非递减顺序** 排列

> ## 二、问题分析 ##
> 
> 因为链表1和链表2都是非递减顺序的，我们可以开辟一条新的链表。当链表1和链表2都不为空时，不断地分别取链表1和链表2中的第一个结点，比较这两个结点哪个小，较小的就在原链表中删除并放入新开辟的链表中。如果相等，我们就人为规定选择链表1。完成上述操作后，将有剩余结点的链表全部插入到新链表后面。
> 
> 我们自始至终使用的是尾插，尾插结点需要链表至少有一个结点。故而会有一种特殊情况：链表中一个结点都没有，我们可以定义一个结果链表，提前预留一个无意义的结点。

> ## 三、完整代码 ##
> 
>     /**
>      * Definition for singly-linked list.
>      * public class ListNode {
>      *     int val;
>      *     ListNode next;
>      *     ListNode() {}
>      *     ListNode(int val) { this.val = val; }
>      *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
>      * }
>      */
>     class Solution {
>             public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
>             ListNode head1=list1;
>             ListNode head2=list2;
>             // 结果链表的头结点 和 尾结点
>             ListNode head=new ListNode(); // 工具结点
>             ListNode last=head;   // 由于现在结果链表中只有一个结点，所以尾结点就是头结点
>             while (head1!=null&&head2!=null){
>                 // head1 代表的链表不是 empty 并且 head2 代表的链表不是 empty
>                 if(head1.val<=head2.val){
>                     // 将 head1 代表的链表头删
>                     ListNode cur=head1;
>                     head1=head1.next;
>                     // 将结点尾插到结果链表中
>                     last.next=cur;
>                     last=cur;
>                 }
>                 else{
>                     ListNode cur=head2;
>                     head2=head2.next;
>                     // 将结点尾插到结果链表中
>                     last.next=cur;
>                     last=cur;
>                 }
>             }
>             if(head1!=null){
>                 last.next=head1;// 把 head1 接到结果链表的后边
>             }
>             else{
>                 last.next=head2;
>             }
>             return head.next;// 跳过工具结点即可
>         }
>     }
> 
> ![2345a67b5b8f42ac91d13c3055ef3423.png][]

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

![fd01e47ca15f41f89cda0c4bb27c87f7.png][]

[21.]: https://leetcode.cn/problems/merge-two-sorted-lists/
[fcbf72d9c72e3cf739efe539b76f397c.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/2ad0f1ec30684035909410318c69f2e3.jpeg
[2345a67b5b8f42ac91d13c3055ef3423.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/a15838560ac04164bd066ced06aa6261.png
[fd01e47ca15f41f89cda0c4bb27c87f7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/0d88f14a1d1642658f6c386c98d0e6de.png