21. 合并两个有序链表【221】 == 剑指 Offer 25. 合并两个排序的链表【6】

淡淡的烟草味﹌ 2023-09-23 15:14 41阅读 0赞

> **难度等级：简单**

> **上一篇算法：**
> 
> [剑指 Offer 24. 反转链表【链表】][Offer 24.]

> **力扣此题地址：**
> 
> [21. 合并两个有序链表 - 力扣（Leetcode）][21. _ - _Leetcode][剑指 Offer 25. 合并两个排序的链表 - 力扣（LeetCode）][Offer 25. _ - _LeetCode]  
>

## 1.题目：合并两个排序的链表 ##

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

## 2.解题思路： ##

> 1.L1和L2两个递增的链表合并成一个递增的链表，将L1和L2链表的结点从头到尾依次比较，如果L1小，就将next指向L1的那个元素，然后指针后移一位，再跟L2那个元素比较，如果L2小，就将next指向L2，指针在L2链表上后移，循环遍历，直到有一个链表遍历完成
> 
> 2.这时会有一个链表还有剩余结点，将剩余结点直接接在新链表后面即可。

![f5b58e9132dd4ae7a42912358d6ac72f.png][]

## 3.代码实现： ##

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
                  // 一开始设置一个虚拟节点，它的值为 -1，它的值可以设置为任何的数，因为我们根本不需要使用它的值
            ListNode dummy = new ListNode(-1);
    
            // 设置一个指针，指向虚拟节点
            ListNode pre = dummy;
    
            // 通过一个循环，不断的比较 l1 和 l2 中当前节点值的大小，直到 l1 或者 l2 遍历完毕为止
            while (l1 != null && l2 != null) {
                // 如果 l1 当前节点的值小于等于了 l2 当前节点的值
                if (l1.val <= l2.val) {
                    // 让 pre 指向节点的 next 指针指向这个更小值的节点
                    // 即指向 l1
                    pre.next = l1;
                    // 让 l1 向后移动
                    l1 = l1.next;
                }else {
                    // 让 pre 指向节点的 next 指针指向这个更小值的节点
                    // 即指向 l2
                    pre.next = l2;
                    // 让 l2 向后移动
                    l2 = l2.next;
    
                }
                // 让 pre 向后移动
                pre = pre.next;
            }
    
            // 跳出循环后，l1 或者 l2 中可能有剩余的节点没有被观察过
            // 直接把剩下的节点加入到 pre 的 next 指针位置
    
            // 如果 l1 中还有节点
            if ( l1 != null) {
                // 把 l1 中剩下的节点全部加入到 pre 的 next 指针位置
                pre.next = l1;
            }
    
            // 如果 l2 中还有节点
            if ( l2 != null) {
                // 把 l2 中剩下的节点全部加入到 pre 的 next 指针位置
                pre.next = l2;
            }
    
            // 最后返回虚拟节点的 next 指针
            return dummy.next;
        }
    }

[Offer 24.]: https://blog.csdn.net/m0_51697147/article/details/127880831
[21. _ - _Leetcode]: https://leetcode.cn/problems/merge-two-sorted-lists/description/
[Offer 25. _ - _LeetCode]: https://leetcode.cn/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/
[f5b58e9132dd4ae7a42912358d6ac72f.png]: https://img-blog.csdnimg.cn/f5b58e9132dd4ae7a42912358d6ac72f.png