hot100链表1题解

发表于 2025/01/16 更新于 2025/01/16

作者 匆匆那年 37 分钟阅读

160. 相交链表

问题描述

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据保证整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

自定义评测：

评测系统 的输入如下（你设计的程序 不适用 此输入）：

intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
listA - 第一个链表
listB - 第二个链表
skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数

评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
— 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。

示例 2：

输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：No intersection
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。

提示：

listA 中节点数目为 m
listB 中节点数目为 n
$1 <= m, n <= 3 * 10^4$
$1 <= Node.val <= 10^5$
0 <= skipA <= m
0 <= skipB <= n
如果 listA 和 listB 没有交点，intersectVal 为 0
如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]

进阶：你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案？

题解

这是一个经典的链表问题，要求找到两个链表的第一个相交节点，或者返回 nullptr 如果它们不相交。我们可以通过双指针法实现，时间复杂度为 $O(m + n)$，空间复杂度为 $O(1)$。

下面是详细的 C++ 代码解法：

  
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(nullptr) {}
 * };
 */

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (!headA || !headB) return nullptr; // 如果任意链表为空，直接返回 null

        ListNode *p1 = headA;
        ListNode *p2 = headB;

        // 两个指针分别遍历链表A和链表B，当到达链表末尾时跳转到另一个链表的头部
        while (p1 != p2) {
            p1 = (p1 == nullptr) ? headB : p1->next;
            p2 = (p2 == nullptr) ? headA : p2->next;
        }

        // 当两个指针相遇时，要么是交点，要么是 null（无交点）
        return p1;
    }
};

解题思路：

双指针法：
- 用两个指针 p1 和 p2 分别遍历链表 A 和 B。
- 如果 p1 到达链表 A 的末尾，则跳转到链表 B 的头部；如果 p2 到达链表 B 的末尾，则跳转到链表 A 的头部。
- 最终，两个指针会在第一个相交节点相遇，或者同时到达链表末尾（nullptr）。
核心原理：
- 两个指针会遍历相同的节点数（$m + n$）。
- 如果存在相交节点，它们会在交点相遇。
- 如果没有交点，两个指针最终都会到达 nullptr。
时间复杂度：
- 每个链表最多遍历两次，因此时间复杂度为 $O(m + n)$。
空间复杂度：
- 仅使用了两个额外指针，空间复杂度为 $O(1)$。

示例运行：

示例 1：

输入：

  
headA = [4,1,8,4,5]
headB = [5,6,1,8,4,5]
skipA = 2, skipB = 3

输出：

  
Intersected at '8'

示例 2：

输入：

  
headA = [1,9,1,2,4]
headB = [3,2,4]
skipA = 3, skipB = 1

输出：

  
Intersected at '2'

示例 3：

输入：

  
headA = [2,6,4]
headB = [1,5]

输出：

No intersection

206. 反转链表

问题描述

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

提示：

链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

题解

以下是解决 反转链表 的两种方法：迭代法 和 递归法。两种方法都有效，具体实现如下：

方法 1：迭代法

使用三个指针 (prev, current, next) 来完成链表反转。

C++ 实现：

  
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(nullptr) {}
 * };
 */

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr; // 用于指向前一个节点
        ListNode* current = head; // 当前节点

        while (current != nullptr) {
            ListNode* next = current->next; // 保存下一个节点
            current->next = prev; // 反转当前节点指针
            prev = current; // 前移 prev
            current = next; // 前移 current
        }

        return prev; // 最终 prev 指向反转后的链表头部
    }
};

思路解析：

用 prev 初始化为 nullptr，用于反转链表的前指针。
遍历链表，通过 current 节点进行操作。
反转当前节点指针，指向前一个节点。
更新指针 prev 和 current，直到链表结束。
返回 prev，即反转后的链表头。

方法 2：递归法

利用递归的特性，反转链表。

C++ 实现：

  
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head; // 如果链表为空或只有一个节点，直接返回头节点
        }

        // 递归反转后面的部分
        ListNode* reversedHead = reverseList(head->next);

        // 反转当前节点
        head->next->next = head; // 下一个节点指向当前节点
        head->next = nullptr; // 当前节点指向空

        return reversedHead; // 返回反转后的头节点
    }
};

思路解析：

递归的终止条件是 head 为 nullptr 或只有一个节点。
递归反转后续节点后，利用链表结构完成反转。
让 head->next->next 指向 head，同时将 head->next 置为 nullptr，从而断开原链表结构。
最终返回新的头节点。

时间与空间复杂度：

方法	时间复杂度	空间复杂度
迭代法	$O(n)$	$O(1)$
递归法	$O(n)$	$O(n)$

示例运行：

示例 1：

输入：

  
head = [1, 2, 3, 4, 5]

输出：

  
[5, 4, 3, 2, 1]

示例 2：

输入：

  
head = [1, 2]

输出：

  
[2, 1]

示例 3：

输入：

  
head = []

输出：

[]

234. 回文链表

问题描述

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：

输入：head = [1,2,2,1]
输出：true

示例 2：

输入：head = [1,2]
输出：false

提示：

链表中节点数目在范围[1, 105] 内
0 <= Node.val <= 9

进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

题解

以下是用 C++ 实现判断链表是否为回文链表的两种方法：

方法一：辅助数组 (时间复杂度 O(n)，空间复杂度 O(n))

我们可以通过遍历链表，将节点的值存储到数组中，然后检查数组是否是回文。

实现代码：

  
#include <vector>
using namespace std;

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

bool isPalindrome(ListNode* head) {
    vector<int> values;
    ListNode* current = head;

    // 将链表的值存储到数组中
    while (current) {
        values.push_back(current->val);
        current = current->next;
    }

    // 使用双指针检查数组是否为回文
    int left = 0, right = values.size() - 1;
    while (left < right) {
        if (values[left] != values[right]) {
            return false;
        }
        ++left;
        --right;
    }

    return true;
}

方法二：快慢指针 + 翻转链表 (时间复杂度 O(n)，空间复杂度 O(1))

使用快慢指针找到链表中间节点，然后翻转链表后半部分，再进行比较。

实现代码：

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

ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    while (head) {
        ListNode* nextTemp = head->next;
        head->next = prev;
        prev = head;
        head = nextTemp;
    }
    return prev;
}

bool isPalindrome(ListNode* head) {
    if (!head || !head->next) {
        return true;
    }

    // 使用快慢指针找到中间节点
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }

    // 翻转后半部分链表
    ListNode* secondHalf = reverseList(slow);

    // 比较前半部分和后半部分
    ListNode* firstHalf = head;
    ListNode* secondHalfCopy = secondHalf; // 用于后续恢复链表
    while (secondHalf) {
        if (firstHalf->val != secondHalf->val) {
            return false;
        }
        firstHalf = firstHalf->next;
        secondHalf = secondHalf->next;
    }

    // 恢复链表（可选）
    reverseList(secondHalfCopy);

    return true;
}

方法二的说明：

找到中间节点： 使用快慢指针，快指针移动两步，慢指针移动一步。当快指针到达末尾时，慢指针正好位于链表中间。
翻转链表： 从中间节点开始翻转链表后半部分。
比较两部分： 使用两个指针分别从链表的头部和翻转后的部分逐一比较节点值。
恢复链表（可选）： 为了不改变链表结构，可以在最后恢复链表。

复杂度分析：

时间复杂度： O(n)，找到中间节点、翻转链表和比较节点各需要 O(n) 时间。
空间复杂度： O(1)，因为我们在原地操作链表。

使用方法二可以满足题目要求，同时优化了空间复杂度。

141. 环形链表

问题描述

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。否则，返回 false 。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

提示：

链表中节点的数目范围是 [0, $10^4$]
-10^5 <= Node.val <= 10^5
pos 为 -1 或者链表中的一个 有效索引 。

进阶：你能用 O(1)（即，常量）内存解决此问题吗？

题解

用 C++ 实现判断链表是否有环，可以用以下两种方法：

方法一：哈希表 (时间复杂度 O(n)，空间复杂度 O(n))

用一个哈希表记录访问过的节点，如果某个节点重复出现，则说明链表中存在环。

实现代码：

  
#include <unordered_set>
using namespace std;

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

bool hasCycle(ListNode* head) {
    unordered_set<ListNode*> visited;
    ListNode* current = head;

    while (current) {
        if (visited.count(current)) {
            return true;
        }
        visited.insert(current);
        current = current->next;
    }

    return false;
}

方法二：快慢指针 (时间复杂度 O(n)，空间复杂度 O(1))

使用两个指针，一个快指针 fast 和一个慢指针 slow。快指针每次移动两步，慢指针每次移动一步。如果链表中有环，两个指针必然会相遇。

实现代码：

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

bool hasCycle(ListNode* head) {
    if (!head || !head->next) {
        return false;
    }

    ListNode* slow = head;
    ListNode* fast = head;

    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;

        // 如果快慢指针相遇，则有环
        if (slow == fast) {
            return true;
        }
    }

    return false;
}

方法二的解释：

初始化指针：
- 快指针 fast 和慢指针 slow 都从链表头部开始。
快慢指针移动：
- 快指针每次移动两步，慢指针每次移动一步。
判断是否相遇：
- 如果链表中有环，快指针会在环中追上慢指针。
- 如果链表中没有环，快指针会在到达链表末尾时变为 nullptr。

复杂度分析：

时间复杂度：
O(n)
- 快慢指针最多遍历链表中的每个节点一次。
空间复杂度：
- 方法一使用哈希表，需要 O(n) 空间。
- 方法二使用常量额外空间，空间复杂度为 O(1)。

142. 环形链表 II

问题描述

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。

提示：

链表中节点的数目范围在范围 $[0, 10^4]$ 内
$-10^5 <= Node.val <= 10^5$
pos 的值为 -1 或者链表中的一个有效索引

进阶：你是否可以使用 O(1) 空间解决此题？

题解

这道题可以用Floyd 判圈算法（快慢指针）来解决，满足题目要求的 $O(1)$ 空间复杂度。以下是具体思路和代码实现：

解题思路

判断是否存在环：
- 使用快慢指针：
  - 快指针每次走两步。
  - 慢指针每次走一步。
- 如果链表中存在环，快慢指针一定会在环中相遇。
- 如果链表没有环，快指针会率先到达链表末尾。
找到环的起点：
- 假设从链表头到环起点的距离为 $a$，环起点到相遇点的距离为 $b$，环的长度为 $L$。
- 当快慢指针相遇时，快指针走的总步数是慢指针的两倍，且有： $2 \times (a + b) = a + b + n \times L$ 化简得：$a = n \times L - b$ 说明从链表头到环起点的距离 $a$ 等于从相遇点沿环走 $n \times L - b$ 的距离。
- 因此，当两个指针分别从链表头和相遇点出发，每次走一步，它们会在环的起点相遇。

C++ 代码实现

  
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if (!head || !head->next) return nullptr;

        ListNode *slow = head;
        ListNode *fast = head;

        // 判断是否有环
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;

            if (slow == fast) { // 快慢指针相遇
                // 找到环的起点
                ListNode *entry = head;
                while (entry != slow) {
                    entry = entry->next;
                    slow = slow->next;
                }
                return entry; // 返回环的起点
            }
        }

        return nullptr; // 没有环
    }
};

示例讲解

示例 1

输入：head = [3,2,0,-4], pos = 1 输出：返回索引为 1 的节点。

快慢指针相遇在值为 -4 的节点。
从头节点和相遇点分别出发，最终在值为 2 的节点相遇。

示例 2

输入：head = [1,2], pos = 0 输出：返回索引为 0 的节点。

快慢指针相遇在值为 2 的节点。
从头节点和相遇点分别出发，最终在值为 1 的节点相遇。

示例 3

输入：head = [1], pos = -1 输出：返回 null。

快指针直接到达链表末尾，无环存在。

时间和空间复杂度分析

时间复杂度：
$O(n)$
- 快慢指针最多遍历链表两次。
空间复杂度：
$O(1)$
- 只使用了两个指针变量。

这段代码满足题目的进阶要求，效率高且实现简洁。

21. 合并两个有序链表

问题描述

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列

题解

解题思路

要将两个升序链表合并为一个新的升序链表，我们可以采用两种方法：迭代法和递归法。以下是详细的实现和代码示例。

方法 1：迭代法

创建一个哨兵节点 dummy 和一个当前指针 current，用于构建新链表。
遍历两个链表，比较当前节点的值，将较小值的节点连接到 current 后面，并移动指针。
当其中一个链表遍历完毕时，将另一个链表剩余部分直接连接到 current。
返回哨兵节点的下一个节点 dummy->next 作为结果。

C++ 实现

  
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode dummy; // 哨兵节点
        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;
    }
};

方法 2：递归法

比较两个链表的头节点，将较小值的节点作为结果链表的当前节点。
递归地处理剩余部分，连接到当前节点的 next。
当某一个链表为空时，返回另一个链表作为剩余部分。

C++ 实现

  
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        // 递归终止条件
        if (!l1) return l2;
        if (!l2) return l1;

        if (l1->val <= l2->val) {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        } else {
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
};

示例讲解

示例 1

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

比较头节点：1 <= 1，取 1。
递归合并剩余部分，依次选择：1 → 2 → 3 → 4 → 4。

示例 2

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

两个链表为空，直接返回空。

示例 3

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

一个链表为空，返回另一个链表。

时间和空间复杂度

方法 1：迭代法

时间复杂度： $O(m + n)$，其中 $m$ 和 $n$ 是两个链表的长度。
空间复杂度： $O(1)$，只使用了常量额外空间。

方法 2：递归法

时间复杂度： $O(m + n)$。
空间复杂度： $O(m + n)$，递归调用栈的深度为 $m + n$。

两种方法中，迭代法更高效且推荐使用，因为它的空间复杂度更低。

2. 两数相加

问题描述

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

示例 2：

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

示例 3：

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

提示：

每个链表中的节点数在范围 [1, 100] 内
0 <= Node.val <= 9
题目数据保证列表表示的数字不含前导零

题解

解题思路

这道题的核心是模拟两个数字按位相加的过程，关键在于处理以下几点：

逐位相加： 从两个链表的头节点开始相加，同时处理进位。
进位处理： 每次相加都需要记录是否有进位（大于 9 时）。
处理剩余节点： 当一个链表比另一个链表长时，需要继续处理剩余节点。
处理最终进位： 如果遍历完成后还有进位，需要额外添加一个节点。

C++ 代码实现

  
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode dummy; // 哨兵节点
        ListNode* current = &dummy; // 当前节点指针
        int carry = 0; // 进位

        // 遍历两个链表
        while (l1 || l2 || carry) {
            int sum = carry; // 初始值为进位
            if (l1) {
                sum += l1->val;
                l1 = l1->next;
            }
            if (l2) {
                sum += l2->val;
                l2 = l2->next;
            }

            carry = sum / 10; // 更新进位
            current->next = new ListNode(sum % 10); // 创建新节点
            current = current->next; // 移动当前指针
        }

        return dummy.next; // 返回结果链表
    }
};

示例讲解

示例 1

输入：l1 = [2,4,3], l2 = [5,6,4] 输出：[7,0,8]

第 1 位：2 + 5 = 7，无进位。
第 2 位：4 + 6 = 10，结果为 0，进位为 1。
第 3 位：3 + 4 + 1 = 8，无进位。

示例 2

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

只有一位，0 + 0 = 0。

示例 3

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] 输出：[8,9,9,9,0,0,0,1]

第 1 位：9 + 9 = 18，结果为 8，进位为 1。
第 2 位：9 + 9 + 1 = 19，结果为 9，进位为 1。
第 3 位：9 + 9 + 1 = 19，结果为 9，进位为 1。
第 4 位：9 + 9 + 1 = 19，结果为 9，进位为 1。
第 5 位：9 + 0 + 1 = 10，结果为 0，进位为 1。
第 6 位：9 + 0 + 1 = 10，结果为 0，进位为 1。
第 7 位：9 + 0 + 1 = 10，结果为 0，进位为 1。
第 8 位：进位 1，结果为 1。

时间和空间复杂度

时间复杂度

时间复杂度：
$O(\max(m, n))$，其中 $m$ 和 $n$ 分别是两个链表的长度。
- 每次只遍历一次两个链表。

空间复杂度

空间复杂度： $O(\max(m, n))$，由于需要存储结果链表，长度最多为 $\max(m, n) + 1$。

该代码逻辑清晰，效率高，能够正确处理所有边界情况。

leetcode, hot100

本文由作者按照 CC BY 4.0 进行授权

160. 相交链表

问题描述

题解

解题思路：

示例运行：

示例 1：

示例 2：

示例 3：

206. 反转链表

问题描述

题解

方法 1：迭代法

C++ 实现：

思路解析：

方法 2：递归法

C++ 实现：

思路解析：

时间与空间复杂度：

示例运行：

示例 1：

示例 2：

示例 3：

234. 回文链表

问题描述

题解

方法一：辅助数组 (时间复杂度 O(n)，空间复杂度 O(n))

实现代码：

方法二：快慢指针 + 翻转链表 (时间复杂度 O(n)，空间复杂度 O(1))

实现代码：

方法二的说明：

复杂度分析：

141. 环形链表

问题描述

题解

方法一：哈希表 (时间复杂度 O(n)，空间复杂度 O(n))

实现代码：

方法二：快慢指针 (时间复杂度 O(n)，空间复杂度 O(1))

实现代码：

方法二的解释：

复杂度分析：

推荐：

142. 环形链表 II

问题描述

题解

解题思路

C++ 代码实现

示例讲解

示例 1

示例 2

示例 3

时间和空间复杂度分析

21. 合并两个有序链表

问题描述

题解

解题思路

方法 1：迭代法

C++ 实现

方法 2：递归法

C++ 实现

示例讲解

示例 1

示例 2

示例 3

时间和空间复杂度

方法 1：迭代法

方法 2：递归法

2. 两数相加

问题描述

题解

解题思路

C++ 代码实现

示例讲解

示例 1

示例 2

示例 3

时间和空间复杂度

时间复杂度

空间复杂度

热门标签