21. 合并两个有序链表

Bin大约 3 分钟

21. 合并两个有序链表

合并两个有序链表

题目描述

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

示例 1：

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

示例 2：

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

示例 3：

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

解题思路

1. 双指针法

由于给定的链表是升序的，我们可以利用双指针法来高效地合并两个链表。

使用两个指针分别指向两个链表的头部，比较它们指向的节点的值，较小的节点加入到新链表中，并移动相应链表的指针。
重复这个过程，直到两个链表都被遍历完。
如果其中一个链表已经遍历完，那么将另一个链表剩余的部分直接连接到新链表的尾部。

2. 处理空链表的情况

如果其中一个链表为空，直接返回另一个链表。
如果两个链表都为空，返回一个空链表。

代码实现

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取第一个链表
        String[] list1Values = scanner.nextLine().split(" ");
        ListNode l1 = null;
        ListNode tail1 = null;
        for (String val : list1Values) {
            if (!val.isEmpty()) {
                ListNode newNode = new ListNode(Integer.parseInt(val));
                if (l1 == null) {
                    l1 = newNode;
                    tail1 = newNode;
                } else {
                    tail1.next = newNode;
                    tail1 = newNode;
                }
            }
        }

        // 读取第二个链表
        String[] list2Values = scanner.nextLine().split(" ");
        ListNode l2 = null;
        ListNode tail2 = null;
        for (String val : list2Values) {
            if (!val.isEmpty()) {
                ListNode newNode = new ListNode(Integer.parseInt(val));
                if (l2 == null) {
                    l2 = newNode;
                    tail2 = newNode;
                } else {
                    tail2.next = newNode;
                    tail2 = newNode;
                }
            }
        }

        Solution solution = new Solution();
        ListNode result = solution.mergeTwoLists(l1, l2);

        // 输出合并后的链表
        while (result != null) {
            System.out.print(result.val + " ");
            result = result.next;
        }
        System.out.println();

        scanner.close();
    }
}

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // 创建一个虚拟头节点，用来简化代码的处理
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;

        // 双指针法合并链表
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                current.next = l1;  // 将较小的节点添加到当前链表
                l1 = l1.next;       // 移动l1指针
            } else {
                current.next = l2;  // 将较小的节点添加到当前链表
                l2 = l2.next;       // 移动l2指针
            }
            current = current.next;  // 移动当前指针
        }

        // 处理剩余的节点
        if (l1 != null) {
            current.next = l1;
        } else {
            current.next = l2;
        }

        return dummy.next;  // 返回合并后的链表（跳过虚拟头节点）
    }
}

// 定义链表节点
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

代码详解

初始化虚拟头节点：
- dummy 是一个虚拟的头节点，它的值是任意的（这里使用了 0），目的是为了方便代码的实现，避免处理空链表的情况。
- current 指针用来在合并过程中追踪新链表的尾部。
双指针合并过程：
- 使用 l1 和 l2 两个指针分别指向两个链表的头节点。
- 比较 l1 和 l2 当前指向节点的值，将较小的节点连接到 current.next，并更新相应的指针（l1 或 l2）。
- 然后移动 current 指针到新链表的尾部。
处理剩余部分：
- 当遍历完其中一个链表时，另一个链表可能还有剩余节点，直接将剩余部分连接到新链表尾部。
返回合并后的链表：
- 最后返回 dummy.next，即合并后的链表（跳过虚拟头节点）。