数据结构与算法--链表

博主：梅零落
发布时间：2022 年 09 月 05 日
233 次浏览
暂无评论
2647字数
分类：数据结构与算法

# 单链表

单链表中的每个结点不仅包含值，还包含链接到下一个结点的引用字段。通过这种方式，单链表将所有结点按顺序组织起来。

下面是一个单链表的例子：
![singleLinkedList.png](https://www.imgyh.com/usr/uploads/2022/09/1518715053.png)

与数组不同，我们无法在常量时间内访问单链表中的随机元素。 如果我们想要获得第 i 个元素，我们必须从头结点逐个遍历。 我们按索引来访问元素平均要花费 O(N) 时间，其中 N 是链表的长度。

## 添加节点

如果我们想在给定的结点 `prev` 之后添加新值，我们应该：

1. 使用给定值初始化新结点 `cur`
   ![singleLinkedListAdd1.png](https://www.imgyh.com/usr/uploads/2022/09/2391896136.png)
2. 将 `cur` 的 `next` 字段链接到 `prev` 的下一个结点 `next` ；
   ![singleLinkedListAdd2.png](https://www.imgyh.com/usr/uploads/2022/09/2060456679.png)
3. 将 `prev` 中的 `next` 字段链接到 `cur`。
   ![singleLinkedListAdd3.png](https://www.imgyh.com/usr/uploads/2022/09/3265061841.png)

我们使用头结点来代表整个列表。因此，在列表开头添加新节点时更新头结点 head 至关重要。
在开头添加结点，我们应该：

1. 初始化一个新结点 `cur` ；
2. 将新结点链接到我们的原始头结点 `head`。
3. 将 `cur` 指定为 `head` 。

## 删除节点

如果我们想从单链表中删除现有结点 `cur`，可以分两步完成：

1. 找到 cur 的上一个结点 `prev` 及其下一个结点 `next` ；
   ![singleLinkedListDelete1.png](https://www.imgyh.com/usr/uploads/2022/09/1936704574.png)
2. 接下来链接 `prev` 到 cur 的下一个节点 `next` 。
   ![singleLinkedListDelete2.png](https://www.imgyh.com/usr/uploads/2022/09/3464104423.png)

在我们的第一步中，我们需要找出 `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 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
![circularlinkedlist.png](https://www.imgyh.com/usr/uploads/2022/09/1060203431.png)

**示例 2：**
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。
![circularlinkedlist_test2.png](https://www.imgyh.com/usr/uploads/2022/09/3416383356.png)

**示例 3：**
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。
![circularlinkedlist_test3.png](https://www.imgyh.com/usr/uploads/2022/09/2288379682.png)

**提示：**

链表中节点的数目范围在范围 [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 每次向后移动一个位置。最终，它们会在入环点相遇。

![142_fig1.png](https://www.imgyh.com/usr/uploads/2022/09/4073913648.png)

**代码：**

```
/**
 * 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：**

![remove_ex1.jpg](https://www.imgyh.com/usr/uploads/2022/09/748560807.jpg)

输入：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：**
![rev1ex1.jpg](https://www.imgyh.com/usr/uploads/2022/09/3358899696.jpg)

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

**示例 2：**
![rev1ex2.jpg](https://www.imgyh.com/usr/uploads/2022/09/3291918960.jpg)

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

**示例 3：**

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

**提示：**

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

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

**算法：**

首先我们建立一个 `dummy` 节点，并将 `dummy` 的 `next` 指向 `head` 。每次循环将 `head` 节点的下一个节点放到 `dummy` 节点之后，直到 `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` 引用字段。

![DoubleLinkedList.png](https://www.imgyh.com/usr/uploads/2022/09/1065567127.png)

## 添加节点

如果我们想在现有的结点 `prev` 之后插入一个新的结点 `cur`，我们可以将此过程分为两个步骤：

1. 链接 `cur` 与 `prev` 和 `next`，其中 `next` 是 `prev` 原始的下一个节点；
   ![DoubleLinkedListAdd1.png](https://www.imgyh.com/usr/uploads/2022/09/3111580309.png)
2. 用 `cur` 重新链接 `prev` 和 `next`。
   ![DoubleLinkedListAdd2.png](https://www.imgyh.com/usr/uploads/2022/09/2516444484.png)
   与单链表类似，添加操作的时间和空间复杂度都是 O(1)。

## 删除节点

如果我们想从双链表中删除一个现有的结点 `cur`，我们可以简单地将它的前一个结点 `prev` 与下一个结点 `next` 链接起来。
![DoubleLinkedListDelete.png](https://www.imgyh.com/usr/uploads/2022/09/3288968432.png)

# 小结

单链表和双链表它们在许多操作中是相似的。

1. 它们都无法在常量时间内随机访问数据。
2. 它们都能够在 O(1) 时间内在给定结点之后或列表开头添加一个新结点。
3. 它们都能够在 O(1) 时间内删除第一个结点。

但是删除给定结点(包括最后一个结点)时略有不同。

- 在单链表中，它无法获取给定结点的前一个结点，因此在删除给定结点之前我们必须花费 O(N) 时间来找出前一结点。
- 在双链表中，这会更容易，因为我们可以使用“prev”引用字段获取前一个结点。因此我们可以在 O(1) 时间内删除给定结点。

![compare.png](https://www.imgyh.com/usr/uploads/2022/09/926559580.png)

如果你需要经常添加或删除结点，链表可能是一个不错的选择。

如果你需要经常按索引访问元素，数组可能是比链表更好的选择。

最后修改：2022 年 12 月 20 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

刚下飞机的大黄
大佬,git上的tiktok项目找不到了, 可以私发我一份么O...
ukyo
我不再看到此条目。https://github.com/img...
九州之子
大佬，是否可以加个获取直播间弹幕相关功能
杰克
大佬，你太牛了！要是能加个验证模块就好了，有时候请求不到数据，...
西门吹风
有时没有返回数据，直接返回两个大括号

BeautifulSoup详解
浏览次数: 462
heroku搭建免费的onemanager
浏览次数: 1845
Ipv4的VPS获取Ipv6地址
浏览次数: 594
Ubuntu 20.04 快速开启TCP BBR
浏览次数: 420
ubuntu安装ohmyzsh
浏览次数: 577

数据结构与算法--链表

梅零落 • 2022 年 09 月 05 日

# 单链表

单链表中的每个结点不仅包含值，还包含链接到下一个结点的引用字段。通过这种方式，单链表将所有结点按顺序组织起来。

下面是一个单链表的例子：
![singleLinkedList.png](https://www.imgyh.com/usr/uploads/2022/09/1518715053.png)

## 添加节点

如果我们想在给定的结点 `prev` 之后添加新值，我们应该：

我们使用头结点来代表整个列表。因此，在列表开头添加新节点时更新头结点 head 至关重要。
在开头添加结点，我们应该：

1. 初始化一个新结点 `cur` ；
2. 将新结点链接到我们的原始头结点 `head`。
3. 将 `cur` 指定为 `head` 。

## 删除节点

如果我们想从单链表中删除现有结点 `cur`，可以分两步完成：

如果想要删除第一个结点，我们可以简单地将下一个结点分配给 `head`。

# 链表中的双指针问题

给定一个链表，判断链表中是否有环。

这正是我们在链表中使用两个速度不同的指针时会遇到的情况：

- 如果没有环，快指针将停在链表的末尾。
- 如果有环，快指针最终将与慢指针相遇。

这两个指针的适当速度应该是多少？

用于解决链表中的双指针问题的模板：

**复杂度分析**

在前面的查找循环示例中，假设我们每次移动较快的指针 2 步，每次移动较慢的指针 1 步。

显然，M <= N 。所以我们将循环运行 N 次。对于每次循环，我们只需要常量级的时间。因此，该算法的时间复杂度总共为 O(N)。

# [142. 环形链表 II](https://leetcode.cn/problems/linked-list-cycle-ii/)

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

不允许修改 链表。

**示例 3：**
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。
![circularlinkedlist_test3.png](https://www.imgyh.com/usr/uploads/2022/09/2288379682.png)

**提示：**

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

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

**算法：**

根据题意，任意时刻，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 圈的环长，恰好等于从链表头部到入环点的距离。

![142_fig1.png](https://www.imgyh.com/usr/uploads/2022/09/4073913648.png)

**代码：**

while (slow != null && fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

**复杂度分析：**

# [19. 删除链表的倒数第 N 个结点](https://leetcode.cn/problems/remove-nth-node-from-end-of-list/)

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

**示例 1：**

![remove_ex1.jpg](https://www.imgyh.com/usr/uploads/2022/09/748560807.jpg)

输入：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

进阶：你能尝试使用一趟扫描实现吗？

**算法：**

在这之后，我们同时使用 first 和 second 对链表进行遍历。当 first 遍历到链表的末尾（即 first 为空指针）时，second 恰好指向倒数第 n 个节点。

**代码：**

**复杂度分析：**

- 时间复杂度：O(L)，其中 L 是链表的长度。
- 空间复杂度：O(1)。

# [206. 反转链表](https://leetcode.cn/problems/reverse-linked-list/)

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

**示例 1：**
![rev1ex1.jpg](https://www.imgyh.com/usr/uploads/2022/09/3358899696.jpg)

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

**示例 2：**
![rev1ex2.jpg](https://www.imgyh.com/usr/uploads/2022/09/3291918960.jpg)

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

**示例 3：**

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

**提示：**

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

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

**算法：**

**代码：**

**复杂度分析：**

# 双链表

双链接列表中的结点具有 `Value` 字段，用于顺序链接结点的 `Next` 引用字段，还有指向前一个节点的 `Prev` 引用字段。

![DoubleLinkedList.png](https://www.imgyh.com/usr/uploads/2022/09/1065567127.png)

## 添加节点

如果我们想在现有的结点 `prev` 之后插入一个新的结点 `cur`，我们可以将此过程分为两个步骤：

## 删除节点

# 小结

单链表和双链表它们在许多操作中是相似的。

但是删除给定结点(包括最后一个结点)时略有不同。

![compare.png](https://www.imgyh.com/usr/uploads/2022/09/926559580.png)

如果你需要经常添加或删除结点，链表可能是一个不错的选择。

如果你需要经常按索引访问元素，数组可能是比链表更好的选择。

数据结构与算法--链表

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

heroku搭建免费的onemanager

qBittorrent一键安装脚本

Rclone挂载OneDrive方法-自建API

基于Vercel部署mac风格网易云音乐

Cloudflare面板使用教程

BeautifulSoup详解

heroku搭建免费的onemanager

Ipv4的VPS获取Ipv6地址

Ubuntu 20.04 快速开启TCP BBR

ubuntu安装ohmyzsh

数据结构与算法--链表

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

数据结构与算法--链表

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款