链表

LeetCode 234 https://leetcode.cn/problems/palindrome-linked-list/description/ 难度：简单 本题需要用到两个知识点，寻找链表的中间节点和反转链表。 首先找到链表的中间节点，然后反转链表的后半段。最后，同时遍历这两段链表，判断值是否相等。 时间复杂度：O(n)，其中 n 是链表的长度（节点个数）。 空间复杂度：O(1)。 ...

LCR 140 https://leetcode.cn/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/description/ 难度：简单 前后指针找链表倒数第 k 个节点。 时间复杂度：O(n)，其中 n 为链表的长度。我们使用快慢指针，只需要一次遍历即可，复杂度为 O(n)。 空间复杂度：O(1)。 ...

LeetCode 2 https://leetcode.cn/problems/add-two-numbers/description/ 难度：中等 递归处理两个链表相加。 时间复杂度：O(n)，其中 n 为 l1 长度和 l2 长度的最大值。 空间复杂度：O(n)。递归需要 O(n) 的栈空间。 ...

LeetCode 148 https://leetcode.cn/problems/sort-list/description/ 难度：中等 本题使用归并排序。 找到链表的中间结点 head 2 的前一个节点，并断开 head2 与其前一个节点的连接。这样我们就把原链表均分成了两段更短的链表。 分治，递归调用 sortList，分别排序 head（只有前一半）和 head2。 排序后，我们得到了两个有序链表，那么合并两个有序链表，得到排序后的链表，返回链表头节点。 时间复杂度：O(nlogn)，其中 n 是链表长度。递归式 T(n)=2T(n/2)+O(n)，由主定理可得时间复杂度为 O(nlogn)。 空间复杂度：O(logn)。递归需要 O(logn) 的栈开销。 ...

LeetCode 82 https://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii/description/ 难度：中等 本题需要删除链表中所有重复数字的节点，只留下不同的数字。为了删除节点，cur 需要在要被删除的节点前面，因此比较 cur->next 和 cur->next->next 的节点值是否相同，如果相同，通过循环将所有等于这个值的节点都删除。否则，更新 cur 到下一个节点。 时间复杂度：O(n)，其中 n 为链表的长度。 空间复杂度：O(1)，仅用到若干额外变量。 ...

LeetCode 19 https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/ 难度：中等 前后指针，右节点先走 n 步，然后左右节点同时走。当右节点走到最后一个节点的时候，左节点就在删除节点的前一个节点。为了处理删除第一个节点的情况，设置 dummy 节点。 时间复杂度：O(m)，其中 m 为链表的长度。 空间复杂度：O(1)，仅用到若干额外变量。 ...

LeetCode 142 https://leetcode.cn/problems/linked-list-cycle-ii/description/ 难度：中等 环形链表 II，比环形链表 I 多了需要找到入环节点。 设头节点到入环口需要走 a 步，环长为 c。快慢指针相遇时，慢指针走了 b 步，快指针走了 2b 步。设快指针比慢指针多走了 k 圈，即 2b - b = kc，得 b = kc。 慢指针在入环口开始，在环中走了 b - a = kc - a 步到达相遇点。这说明从相遇点开始，再走 a 步，就恰好到达相遇点。 如果让头节点和慢指针同时走，恰好 a 步后二者必定相遇，且相遇点就在入环口。 时间复杂度：O(n)，其中 n 为链表的长度。 空间复杂度：O(1)，仅用到若干额外变量。 ...

LeetCode 160 https://leetcode.cn/problems/intersection-of-two-linked-lists/description/ 难度：简单 最简单的方法是使用哈希集合来记录访问过的节点。除此之外还有双指针的做法。 我来到你的城市，走过你来时的路。 初始化两个指针 p = headA, q = headB。 不断循环，直到 p == q。 每次循环，p 和 q 各向后走一步。具体来说，如果 p 不是空节点，那么更新 p 为 p->next，否则更新 p 为 headB；如果 q 不是空节点，那么更新 q 为 q->next，否则更新 q 为 headA。 循环结束时，如果两条链表相交，那么此时 p 和 q 都在相交的起始节点处，返回 p；如果两条链表不相交，那么 p 和 q 都走到空节点，所以也可以返回 p，即空节点。 时间复杂度：O(m+n)，其中 m 是第一条链表的长度，n 是第二条链表的长度。除了交点，每个节点会被指针 p 访问至多一次，每个节点会被指针 q 访问至多一次。 空间复杂度：O(1)。 ...

LeetCode 143 https://leetcode.cn/problems/reorder-list/description/ 难度：中等 这道题目需要先找到链表的中间节点 LeetCode 876，然后反转后半部分的链表 LeetCode 206。 head 指向前半部分头节点，head2 指向后半部分的头节点。每次更新 head->next = head2, head2->next = nxt。 时间复杂度：O(n)，其中 n 为链表的长度。 空间复杂度：O(1)，仅用到若干额外变量。 ...

LeetCode 141 https://leetcode.cn/problems/linked-list-cycle/description/ 难度：简单 这道题目的做法是快慢指针。快指针每次走两步，慢指针每次走一步，如果快慢指针相等，说明链表有环。 时间复杂度：O(n)，其中 n 为链表的长度。 空间复杂度：O(1)，仅用到若干额外变量。 ...