解题思路

1. 使用双指针合并两个有序链表

   • 维护两个指针 l1 和 l2，分别指向 L1 和 L2 的当前节点。
   • 创建一个虚拟头节点 (dummy)，用于连接新链表，简化边界条件的处理。
   • 使用 tail 指针来维护新链表的末尾节点，并逐步扩展链表。

2. 合并链表过程

   • 逐步比较 l1 和 l2 指向的节点值，将较小的节点添加到新链表。
   • 移动相应的指针，使其指向下一个未合并的节点。
   • 当 L1 或 L2 遍历完后，将剩余的部分直接连接到新链表末尾。

3. 特殊情况处理

   • 如果 L1 为空，直接返回 L2。
   • 如果 L2 为空，直接返回 L1。
   • 输出格式：如果合并后的链表为空，则输出空行，否则各节点值以空格分隔。

时间复杂度 & 空间复杂度

• 时间复杂度：O(n + m)，其中 n 和 m 分别是 L1 和 L2 的长度，最多遍历两次。
• 空间复杂度：O(1)，只使用了几个指针变量，不占额外存储空间。

Python 版本

import sys

# 定义链表节点
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# 合并两个有序链表
def merge_two_lists(l1, l2):
    dummy = ListNode()  # 创建虚拟头节点
    current = dummy  # 当前指针

    # 遍历两个链表
    while l1 and l2:
        if l1.val < l2.val:
            current.next = l1  # 选择较小节点
            l1 = l1.next
        else:
            current.next = l2
            l2 = l2.next
        current = current.next  # 移动指针
    
    # 连接剩余链表
    current.next = l1 if l1 else l2
    return dummy.next

# 构造链表
def build_linked_list(values):
    if not values:
        return None
    head = ListNode(values[0])
    current = head
    for val in values[1:]:
        current.next = ListNode(val)
        current = current.next
    return head

# 输出链表（空格分隔）
def print_linked_list(head):
    result = []
    while head:
        result.append(str(head.val))
        head = head.next
    print(" ".join(result))

# 读取输入并处理
def main():
    t = int(sys.stdin.readline().strip())  # 读取测试用例数量
    for _ in range(t):
        n = int(sys.stdin.readline().strip())  # 读取第一个链表大小
        line = sys.stdin.readline().strip()
        l1 = list(map(int, line.split())) if n and line else []
        m = int(sys.stdin.readline().strip())  # 读取第二个链表大小
        line = sys.stdin.readline().strip()
        l2 = list(map(int, line.split())) if m and line else []

        l1_head = build_linked_list(l1)  # 构造链表
        l2_head = build_linked_list(l2)
        merged_head = merge_two_lists(l1_head, l2_head)  # 合并链表
        print_linked_list(merged_head)  # 输出结果

if __name__ == "__main__":
    main()

Java 版本

import java.util.*;

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class Main {
    // 合并两个有序链表
    public static 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;
            } else {
                current.next = l2;
                l2 = l2.next;
            }
            current = current.next; // 移动指针
        }

        current.next = (l1 != null) ? l1 : l2; // 连接剩余链表
        return dummy.next;
    }

    // 构造链表
    public static ListNode buildLinkedList(int[] values) {
        if (values.length == 0) return null;
        ListNode head = new ListNode(values[0]);
        ListNode current = head;
        for (int i = 1; i < values.length; i++) {
            current.next = new ListNode(values[i]);
            current = current.next;
        }
        return head;
    }

    // 输出链表（空格分隔）
    public static void printLinkedList(ListNode head) {
        StringBuilder sb = new StringBuilder();
        while (head != null) {
            sb.append(head.val).append(" ");
            head = head.next;
        }
        System.out.println(sb.toString().trim());
    }

    // 读取输入并处理
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt(); // 读取测试用例数量
        while (t-- > 0) {
            int n = sc.nextInt(); // 读取第一个链表大小
            int[] l1 = new int[n];
            for (int i = 0; i < n; i++) l1[i] = sc.nextInt();

            int m = sc.nextInt(); // 读取第二个链表大小
            int[] l2 = new int[m];
            for (int i = 0; i < m; i++) l2[i] = sc.nextInt();

            ListNode l1Head = buildLinkedList(l1); // 构造链表
            ListNode l2Head = buildLinkedList(l2);
            ListNode mergedHead = mergeTwoLists(l1Head, l2Head); // 合并链表
            printLinkedList(mergedHead); // 输出结果
        }
        sc.close();
    }
}

C++ 版本

#include <iostream>
#include <vector>

using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int val) : val(val), next(nullptr) {}
};

// 合并两个有序链表
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode dummy(0); // 创建虚拟头节点
    ListNode* current = &dummy; // 当前指针

    while (l1 && l2) {
        if (l1->val < l2->val) {
            current->next = l1; // 选择较小节点
            l1 = l1->next;
        } else {
            current->next = l2;
            l2 = l2->next;
        }
        current = current->next; // 移动指针
    }

    current->next = l1 ? l1 : l2; // 连接剩余链表
    return dummy.next;
}

// 构造链表
ListNode* buildLinkedList(const vector<int>& values) {
    if (values.empty()) return nullptr;
    ListNode* head = new ListNode(values[0]);
    ListNode* current = head;
    for (size_t i = 1; i < values.size(); i++) {
        current->next = new ListNode(values[i]);
        current = current->next;
    }
    return head;
}

// 输出链表（空格分隔）
void printLinkedList(ListNode* head) {
    bool first = true;
    while (head) {
        if (!first) cout << " ";
        cout << head->val;
        head = head->next;
        first = false;
    }
    cout << "\n";
}

int main() {
    int t;
    cin >> t; // 读取测试用例数量
    while (t--) {
        int n;
        cin >> n; // 读取第一个链表大小
        vector<int> l1(n);
        for (int i = 0; i < n; i++) cin >> l1[i];

        int m;
        cin >> m; // 读取第二个链表大小
        vector<int> l2(m);
        for (int i = 0; i < m; i++) cin >> l2[i];

        ListNode* l1Head = buildLinkedList(l1); // 构造链表
        ListNode* l2Head = buildLinkedList(l2);
        ListNode* mergedHead = mergeTwoLists(l1Head, l2Head); // 合并链表
        printLinkedList(mergedHead); // 输出结果
    }
    return 0;
}

Leetcode 27.合并两个有序链表-原题链接

题目描述

给定两个升序链表 L1 和 L2，将它们合并为一个新的升序链表并返回。新链表由拼接 L1 和 L2 的所有节点组成。

输入描述

输入包含多组测试数据。

第一行输入一个整数 T（$1 \leq T \leq 100$），表示测试用例的数量。

对于每个测试用例：

• 第一行输入一个整数 n（$0 \leq n \leq 50$），表示链表 L1 的节点数。
• 第二行输入 n 个整数，表示 L1 中的元素（按非递减顺序排列）。
• 第三行输入一个整数 m（$0 \leq m \leq 50$），表示链表 L2 的节点数。
• 第四行输入 m 个整数，表示 L2 中的元素（按非递减顺序排列）。

如果 L1 或 L2 为空，则该行不输入任何数。

输出描述

对于每个测试用例，输出一行，表示合并后的升序链表。

如果合并后的链表为空，则直接输出一个空行。

样例输入

3
3
1 2 4
3
1 3 4
0

0

3
1 3 5
1
2

样例输出

1 1 2 3 4 4

1 2 3 5

提示

• 链表的节点值范围：$-100 \leq \text{Node.val} \leq 100$。
• L1 和 L2 均按非递减顺序排列。