LeetCode题练习与总结：合并两个有序链表

一、题目概述

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

二、解题思路

1. 创建一个新的虚拟头节点，这个节点不会包含任何实际的值，它的目的是为了简化边界条件处理，比如在合并完成后直接返回头节点的下一个节点作为新链表的头节点。
2. 创建一个当前指针（current），初始指向虚拟头节点。
3. 使用两个指针分别指向两个链表的当前节点，分别为p1和p2，初始时p1指向list1的头节点，p2指向list2的头节点。
4. 进入一个循环，循环条件是p1和p2都不为空。
5. 在每次循环中，比较p1和p2的值，将较小的节点连接到current后面，然后将对应的指针向前移动一位。
6. 如果其中一个链表的指针已经移动到末尾，将另一个链表剩余的所有节点连接到current后面。
7. 当两个链表的所有节点都处理完毕后，返回虚拟头节点的下一个节点，即新链表的头节点。

三、具体代码

class Solution {    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {        // 创建虚拟头节点        ListNode dummy = new ListNode(0);        // 当前指针，初始指向虚拟头节点        ListNode current = dummy;                // 初始化两个链表的指针        ListNode p1 = list1, p2 = list2;                // 当两个链表都不为空时循环        while (p1 != null && p2 != null) {            // 比较两个节点的值，选择较小的节点            if (p1.val  
四、时间复杂度与空间复杂度
 
这段代码的时间复杂度是 O(m + n)，空间复杂度是 O(1)。
 
1. 时间复杂度
 

• 代码中的循环会遍历两个链表中的所有元素，直到其中一个链表的所有元素都被处理完毕。
• 在最坏的情况下，即两个链表长度相等，循环会执行大约 m + n 次，其中 m 是 list1 的长度，n 是 list2 的长度。
• 因此，时间复杂度是 O(m + n)。

  2. 空间复杂度

  • 创建了一个虚拟头节点 dummy，它是一个常数级别的额外空间。
  • current 指针在循环中被重复使用，指向新链表的当前节点，这不会增加额外的空间复杂度。
  • 除了输入链表外，没有使用额外的数据结构来存储链表元素，所以空间复杂度是 O(1)，即常数空间复杂度。

    五、总结知识点

    1. 链表（Linked List）：

    （）
    • 链表是一种线性数据结构，其中的元素（节点）按顺序链接在一起。
    • 每个节点包含数据部分（val）和指向下一个节点的指针（next）。

      2. 虚拟头节点（Dummy Node）：

      • 在处理链表问题时，有时会创建一个虚拟头节点，它的目的是简化边界条件的处理，如在合并链表时不需要特别处理头节点。

        3. 指针操作：

        • 使用指针（p1和p2）遍历和操作链表。
        • 在循环中，指针用于比较和选择两个链表中的较小节点，并更新指针以指向下一个节点。

          4. 条件语句（Conditional Statement）：

          • 使用if-else语句来决定哪个节点应该成为新链表的一部分。

            5. 循环（Loop）：

            • 使用while循环来遍历两个链表，直到其中一个链表的所有元素都被处理。

              6. 链表的连接：

              • 在循环中，通过更新current.next来连接两个链表的节点，形成新的链表。

                7. 边界条件处理：

                • 在循环结束后，需要检查两个链表是否还有剩余的节点，如果有，需要将剩余的节点连接到新链表的末尾。