Loading... # 单链表 单链表中的每个结点不仅包含值,还包含链接到下一个结点的引用字段。通过这种方式,单链表将所有结点按顺序组织起来。 下面是一个单链表的例子:  与数组不同,我们无法在常量时间内访问单链表中的随机元素。 如果我们想要获得第 i 个元素,我们必须从头结点逐个遍历。 我们按索引来访问元素平均要花费 O(N) 时间,其中 N 是链表的长度。 ## 添加节点 如果我们想在给定的结点 `prev` 之后添加新值,我们应该: 1. 使用给定值初始化新结点 `cur`  2. 将 `cur` 的 `next` 字段链接到 `prev` 的下一个结点 `next` ;  3. 将 `prev` 中的 `next` 字段链接到 `cur`。  我们使用头结点来代表整个列表。因此,在列表开头添加新节点时更新头结点 head 至关重要。 在开头添加结点,我们应该: 1. 初始化一个新结点 `cur` ; 2. 将新结点链接到我们的原始头结点 `head`。 3. 将 `cur` 指定为 `head` 。 ## 删除节点 如果我们想从单链表中删除现有结点 `cur`,可以分两步完成: 1. 找到 cur 的上一个结点 `prev` 及其下一个结点 `next` ;  2. 接下来链接 `prev` 到 cur 的下一个节点 `next` 。  在我们的第一步中,我们需要找出 `prev` 和 `next`。使用 `cur` 的参考字段很容易找出 `next`,但是,我们必须从头结点遍历链表,以找出 `prev`,它的平均时间是 O(N),其中 N 是链表的长度。因此,删除结点的时间复杂度将是 O(N)。 空间复杂度为 O(1),因为我们只需要常量空间来存储指针。 如果想要删除第一个结点,我们可以简单地将下一个结点分配给 `head`。 # 链表中的双指针问题 给定一个链表,判断链表中是否有环。 想象一下,有两个速度不同的跑步者。如果他们在直路上行驶,快跑者将首先到达目的地。但是,如果它们在圆形跑道上跑步,那么快跑者如果继续跑步就会追上慢跑者。 这正是我们在链表中使用两个速度不同的指针时会遇到的情况: - 如果没有环,快指针将停在链表的末尾。 - 如果有环,快指针最终将与慢指针相遇。 这两个指针的适当速度应该是多少? 一个安全的选择是每次移动慢指针一步,而移动快指针两步。每一次迭代,快速指针将额外移动一步。如果环的长度为 M,经过 M 次迭代后,快指针肯定会多绕环一周,并赶上慢指针。 用于解决链表中的双指针问题的模板: ``` // Initialize slow & fast pointers ListNode slow = head; ListNode fast = head; /** * Change this condition to fit specific problem. * Attention: remember to avoid null-pointer error **/ while (slow != null && fast != null && fast.next != null) { slow = slow.next; // move slow pointer one step each time fast = fast.next.next; // move fast pointer two steps each time if (slow == fast) { // change this condition to fit specific problem return true; } } return false; // change return value to fit specific problem ``` 1. 在调用 next 字段之前,始终检查节点是否为空。 获取空节点的下一个节点将导致空指针错误。例如,在我们运行 fast = fast.next.next 之前,需要检查 fast 和 fast.next 不为空。 2. 仔细定义循环的结束条件。 **复杂度分析** 空间复杂度分析容易。如果只使用指针,而不使用任何其他额外的空间,那么空间复杂度将是 O(1)。但是,时间复杂度的分析比较困难。为了得到答案,我们需要分析运行循环的次数。 在前面的查找循环示例中,假设我们每次移动较快的指针 2 步,每次移动较慢的指针 1 步。 - 如果没有循环,快指针需要 N/2 次才能到达链表的末尾,其中 N 是链表的长度。 - 如果存在循环,则快指针需要 M 次才能赶上慢指针,其中 M 是列表中循环的长度。 显然,M <= N 。所以我们将循环运行 N 次。对于每次循环,我们只需要常量级的时间。因此,该算法的时间复杂度总共为 O(N)。 # [142. 环形链表 II](https://leetcode.cn/problems/linked-list-cycle-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, 104] 内 -105 <= Node.val <= 105 pos 的值为 -1 或者链表中的一个有效索引 进阶:你是否可以使用 O(1) 空间解决此题? **算法:** 我们使用两个指针,fast 与 slow。它们起始都位于链表的头部。随后,slow 指针每次向后移动一个位置,而 fast 指针向后移动两个位置。如果链表中存在环,则 fast 指针最终将再次与 slow 指针在环中相遇。 如下图所示,设链表中环外部分的长度为 a。slow 指针进入环后,又走了 b 的距离与 fast 相遇。此时,fast 指针已经走完了环的 n 圈,因此它走过的总距离为 a+n(b+c)+b=a+(n+1)b+nc。 根据题意,任意时刻,fast 指针走过的距离都为 slow 指针的 22 倍。因此,我们有 a+(n+1)b+nc=2(a+b)⟹a=c+(n−1)(b+c) 有了 a=c+(n-1)(b+c) 的等量关系,我们会发现:从相遇点到入环点的距离加上 n−1 圈的环长,恰好等于从链表头部到入环点的距离。 因此,当发现 slow 与 fast 相遇时,我们再额外使用一个指针 ptr。起始,它指向链表头部;随后,它和 slow 每次向后移动一个位置。最终,它们会在入环点相遇。  **代码:** ``` /** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode detectCycle(ListNode head) { ListNode slow = head; ListNode fast = head; while (slow != null && fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) { ListNode ptr = head; while (ptr != slow) { ptr = ptr.next; slow = slow.next; } return ptr; } } return null; } } ``` **复杂度分析:** - 时间复杂度:O(N),其中 N 为链表中节点的数目。在最初判断快慢指针是否相遇时,slow 指针走过的距离不会超过链表的总长度;随后寻找入环点时,走过的距离也不会超过链表的总长度。因此,总的执行时间为O(N)+O(N)=O(N)。 - 空间复杂度:O(1)。我们只使用了slow,fast,ptr 三个指针。 # [19. 删除链表的倒数第 N 个结点](https://leetcode.cn/problems/remove-nth-node-from-end-of-list/) 给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。 **示例 1:**  输入:head = [1,2,3,4,5], n = 2 输出:[1,2,3,5] **示例 2:** 输入:head = [1], n = 1 输出:[] **示例 3:** 输入:head = [1,2], n = 1 输出:[1] **提示:** 链表中结点的数目为 sz 1 <= sz <= 30 0 <= Node.val <= 100 1 <= n <= sz 进阶:你能尝试使用一趟扫描实现吗? **算法:** 由于我们需要找到倒数第 n 个节点,因此我们可以使用两个指针first 和 second 同时对链表进行遍历,并且 first 比 second 超前 n 个节点。当 first 遍历到链表的末尾时,second 就恰好处于倒数第 n 个节点。 具体地,初始时 first 和 second 均指向头节点。我们首先使用 first 对链表进行遍历,遍历的次数为 n。此时,first 和 second 之间间隔了 n−1 个节点,即 first 比 second 超前了 n 个节点。 在这之后,我们同时使用 first 和 second 对链表进行遍历。当 first 遍历到链表的末尾(即 first 为空指针)时,second 恰好指向倒数第 n 个节点。 如果我们能够得到的是倒数第 n 个节点的前驱节点而不是倒数第 n 个节点的话,删除操作会更加方便。因此我们可以考虑在初始时将 second 指向哑节点,其余的操作步骤不变。这样一来,当 first 遍历到链表的末尾时,second 的下一个节点就是我们需要删除的节点。 **代码:** ``` /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy = new ListNode(0, head); ListNode first = head; ListNode second = dummy; for (int i = 0; i < n; ++i) { first = first.next; } while (first != null) { first = first.next; second = second.next; } second.next = second.next.next; ListNode ans = dummy.next; return ans; } } ``` **复杂度分析:** - 时间复杂度:O(L),其中 L 是链表的长度。 - 空间复杂度:O(1)。 # [206. 反转链表](https://leetcode.cn/problems/reverse-linked-list/) 给你单链表的头节点 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 进阶:链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题? **算法:** 首先我们建立一个 `dummy` 节点,并将 `dummy` 的 `next` 指向 `head` 。每次循环将 `head` 节点的下一个节点放到 `dummy` 节点之后,直到 `head` 到最后一个节点。 **代码:** ``` /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode reverseList(ListNode head) { if (head==null){ return null; } ListNode dummy = new ListNode(0,head); while (head.next!=null){ ListNode temp2 = head.next; ListNode temp3 = dummy.next; dummy.next = temp2; head.next = temp2.next; temp2.next = temp3; } return dummy.next; } } ``` **复杂度分析:** - 时间复杂度:在该算法中,每个结点`只移动一次`。因此,时间复杂度为 `O(N)`,其中 N 是链表的长度。 - 空间复杂度: 我们只使用常量级的额外空间,所以空间复杂度为 `O(1)。` # 双链表 双链接列表中的结点具有 `Value` 字段,用于顺序链接结点的 `Next` 引用字段,还有指向前一个节点的 `Prev` 引用字段。  ## 添加节点 如果我们想在现有的结点 `prev` 之后插入一个新的结点 `cur`,我们可以将此过程分为两个步骤: 1. 链接 `cur` 与 `prev` 和 `next`,其中 `next` 是 `prev` 原始的下一个节点;  2. 用 `cur` 重新链接 `prev` 和 `next`。  与单链表类似,添加操作的时间和空间复杂度都是 O(1)。 ## 删除节点 如果我们想从双链表中删除一个现有的结点 `cur`,我们可以简单地将它的前一个结点 `prev` 与下一个结点 `next` 链接起来。  # 小结 单链表和双链表它们在许多操作中是相似的。 1. 它们都无法在常量时间内随机访问数据。 2. 它们都能够在 O(1) 时间内在给定结点之后或列表开头添加一个新结点。 3. 它们都能够在 O(1) 时间内删除第一个结点。 但是删除给定结点(包括最后一个结点)时略有不同。 - 在单链表中,它无法获取给定结点的前一个结点,因此在删除给定结点之前我们必须花费 O(N) 时间来找出前一结点。 - 在双链表中,这会更容易,因为我们可以使用“prev”引用字段获取前一个结点。因此我们可以在 O(1) 时间内删除给定结点。  如果你需要经常添加或删除结点,链表可能是一个不错的选择。 如果你需要经常按索引访问元素,数组可能是比链表更好的选择。 最后修改:2022 年 12 月 20 日 © 允许规范转载 打赏 赞赏作者 支付宝微信 赞 0 如果觉得我的文章对你有用,请随意赞赏