剑指 Offer 25: 合并两个排序的链表

[songyy5517]

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

示例1：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

分析 根据题意，一个很直接的想法就是比较从头到尾链表，将每次的较小值放入新链表中。

[songyy5517]

思路1：递归

1. 特殊值处理/递归出口；
2. 定义合并后链表的头节点；
3. 递归合并链表： （1）将较小值赋给头节点； （2）递归合并剩下的节点。
4. 返回头节点。

复杂度分析

• 时间复杂度： $O(M+N)$ , $N, M$ 分别是两个链表的大小
• 空间复杂度： $O(M+N)$ , 递归的深度为 $N+M$ , 即系统会使用 $O(M+N)$ 的栈空间

[songyy5517]

/**
 * 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) {
        // 0. 特殊值处理/递归出口
        if (l1 == null || l2 == null)
            if (l1 == null)
                return l2;
            else
                return l1;

        // 1. 创建合并后的链表
        ListNode head = new ListNode();    // 递归方法中无需设置伪头节点（2023/2/8）

        // 2. 递归合并链表
        if (l1.val <= l2.val){
            head.val = l1.val;
            head.next = mergeTwoLists(l1.next, l2);
        }
        else{
            head.val = l2.val;
            head.next = mergeTwoLists(l1, l2.next);
        }

        // 3. 返回合并后链表的头节点
        return head;

    }
}

[songyy5517]

思路2：循环合并

1. 特殊值处理
2. 创建辅助节点作为合并链表的伪头节点
3. 循环合并链表，直到有一个链表为空 (1) 比较两链表头节点的值，将当前指针指向较小者所在的链表 (2) 原指针向后移动一步 (3) 更新当前指针
4. 将非空链表作为合并链表剩下的部分，并返回合并链表的头节点 (伪头节点的下一个节点)

复杂度分析：

• 时间复杂度 $O(N+M)$ ： $M$ , $N$ 分别表示链表1和链表2的长度
• 空间复杂度 $O(1)$ ：常数级空间

[songyy5517]

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 10:17-
     * @param pHead1 ListNode类
     * @param pHead2 ListNode类
     * @return ListNode类
     */
    public ListNode Merge (ListNode pHead1, ListNode pHead2) {
        // write code here
        // 思路：循环比较。

        // 1. 异常处理
        if (pHead1 == null || pHead2 == null)
            return pHead1 == null ? pHead2 : pHead1;

        // 2. 定义双指针
        ListNode p1 = pHead1, p2 = pHead2;
        ListNode pseudo_head = new ListNode(0);    // 伪头节点
        ListNode res = pseudo_head;  // 最终链表

        // 3. 比较链表元素
        while (p1 != null && p2 != null) {
            if (p1.val < p2.val) {
                res.next = p1;
                p1 = p1.next;
            } else {
                res.next = p2;
                p2 = p2.next;
            }
            res = res.next;
        }

        res.next = p1 == null ? p2 : p1;
        return pseudo_head.next;    // 返回伪头节点以外的节点
    }
}

[songyy5517]

2023/2/8 思路2：循环合并

1. 合并过程无需新建节点
2. 记得更新当前的节点指针
3. 判断赋值语句的高级写法

思路1：递归合并

1. 递归合并过程中，无需设置伪头节点

2024/1/13

1. 通过只是伪头节点来解决首次操作；
2. 合并过程无需新建节点：将新链表的下一个节点指向两链表中较小的节点，同时更新新链表和较小的链表指针。