2024年最全【数据结构与算法】链表2W字终极无敌总结

1. 数据域：存放信息的位置
2. 指针域：结点之间相连的关键（可以看成火车之间的连接的链子）
3. 自身地址：即结点本身的位置，指针域连接的就是这个部分。（可以看成每一节车厢的编号）

在下面的介绍中，会发现将创建结点的代码单独放在了一个函数中，我们知道，一个变量出了函数的作用域会由于栈帧的操作释放该变量，导致返回值不能使用，但是这个为什么可以呢？

当然，通过malloc等动态开辟的空间不会主动释放，其开辟的空间是在堆空间上实现的，并不是栈；在之前的动态内存开辟中，说明了这一类的只能由free函数释放掉，并且一定要及时的释放掉，否则会发生内存泄漏。

2.2 链表的分类

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

1. 单向或者双向
   
2. 带头或者不带头

3. 循环或者非循环

虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：

1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。

2.3 链表的实现

2.3.1 具体功能函数

// 1、无头+单向+非循环链表增删查改实现
typedef int SLTDataType;
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode\* next;
}SLTNode;

// 动态申请一个结点
SLTNode\* BuySLTNode(SLTDataType x);
// 单链表打印
void SListPrint(SLTNode\* phead);
//单链表销毁
void SListDestory(SLTNode\*\* pphead);
// 单链表的头插
void SListPushFront(SLTNode\*\* pphead, SLTDataType x);
// 单链表尾插
void SListPushBack(SLTNode\*\* pphead, SLTDataType x);
// 单链表的尾删
void SListPopBack(SLTNode\*\* pphead);
// 单链表头删
void SListPopFront(SLTNode\*\* pphead);
// 单链表查找
SLTNode\* SListFind(SLTNode\* phead, SLTDataType x);
// 在pos之前插入
void SListInsert(SLTNode\*\* pphead, SLTNode\* pos, SLTDataType x);
// 在pos后面插入
void SListInsertAfter(SLTNode\* pos, SLTDataType x);
// 删除pos位置
void SListErase(SLTNode\*\* pphead, SLTNode\* pos);

// 删除pos后面位置
void SListEraseAfter(SLTNode\* pos);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

在实现之前，我们需要先弄懂每个函数传参的参数类型不一样的原因是什么？

• 不难发现，传二级的原因是需要改头，因为头的类型原本就是SLTNode* 类型的，如果函数参数也为此类型，则函数改变的将会是形参，形参只是实参的一份临时拷贝，改变形参，实参不会发生改变，因此，当我们需要改头时，在test.c中传入的应该是：函数名(&plist),而因为plist是头，故定义的时候就是 SLTNode plist*，因此，需要传入二级指针。

2.3.2 代码：

由于本篇文章过长，为了不占用过多篇幅影响小伙伴们食用，单链表实现的代码点下方链接即可（这是我的代码仓库的部分呜呜呜）：

单链表实现的代码在这里呦

当我们梳理完整的代码之后，单链表的优势和缺陷也就显而易见了：

优势： 头插头删，时间复杂度为O(1)。

缺陷：当我们想要删除除了头的任何一个当前位置时，需要记录他的前一个节点，这就需要去寻找这个节点，因此时间复杂度为O(N)。

既然有缺陷，那么有没有方式去弥补这个缺陷呢？

想要删除当前节点的数据，若是能通过删除下一个节点从而删除当前节点岂不是完美了吗，于是，在这里用一种方式：将下一个节点的数据覆盖到当前的节点的数据之上，再将下一个节点删除。 这样，我们通过数据的迁移间接性的将此位置的节点删除，并且时间复杂度是O(1)。

但实际上，这不过是一个取巧的方式而已，链表终究只是适合头部的改变，尾部改变还不如用顺序表。

由于链表的oj题极为重要，作者将会对典型题目进行详细的讲解：( 还不赶紧拍手叫好（滑稽）)

3. LeetCode链表典型题目

3.1 移除链表元素

203. 移除链表元素

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

示例 1：

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

1
2
3

示例 2：

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

1
2
3

示例 3：

输入：head = [7,7,7,7], val = 7
输出：[]

1
2
3

提示：

• 列表中的节点数目在范围 [0, 104] 内
• 1 <= Node.val <= 50
• 0 <= val <= 50

具体思路： 创建一个新的头节点，但不存储数据，若节点数据不等于val，则将此与其连接，同时记录尾部，方便下一次连接。

代码实现： 时间复杂度为O(N)

//不是val尾插到新链表,对新链表创建个尾指针
struct ListNode\* removeElements(struct ListNode\* head, int val){
    struct ListNode\* newhead = (struct ListNode\*)malloc(sizeof(struct ListNode));
    newhead->next = NULL;
    struct ListNode\* tail = newhead;//哨兵位
    struct ListNode\* cur = head;
    while(cur)
    {
        struct ListNode\* next = cur->next;//记录下一个节点位置
        if(cur->val != val)
        {
            tail->next = cur;
            cur->next = NULL;//断开
            tail = cur;
        }
        cur = next;
    }
    return newhead->next;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

3.2 反转链表

206. 反转链表

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

示例 1：

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

1
2
3

示例 2：

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

1
2
3

示例 3：

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

1
2
3

提示：

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

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

思路：

• 法1：三指针迭代

通过改变箭头的方向从而使链表反向，在截断原本的链接之前，需要用指针记录下一位置，以便进行向后迭代。

直到cur为空。

struct ListNode\* reverseList(struct ListNode\* head) {
    if (head == NULL || head->next == NULL)
        return head;
    struct ListNode\* prev = NULL, \* cur = head, \* next = head->next;
    while (cur)
    {
        //反转链表
        cur->next = prev;
        //迭代
        prev = cur;
        cur = next;
        if (next)
            next = next->next;
    }
    return prev;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

• 法2：头插

创建新头newHead = NULL,将旧链表每一个节点取下来进行头插

struct ListNode\* reverseList(struct ListNode\* head) {
    struct ListNode\* cur = head;
    struct ListNode\* newHead = NULL;
    while (cur)
    {
        struct ListNode\* next = cur->next;
        cur->next = newHead;
        newHead = cur;
        cur = next;
    }
    return newHead;
}

1
2
3
4
5
6
7
8
9
10
11
12
13

3.3 链表的中间结点

876. 链表的中间结点

给定一个头结点为 head 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

示例 1：

输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.

1
2
3
4
5
6

示例 2：

输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。

1
2
3
4

提示：

• 给定链表的结点数介于 1 和 100 之间。

思路： 对于中间节点来说，比较直白的方法是计算链表的长度，折半之后在遍历进行迭代，思路很清晰并且正确。但第二种思路才是这个题中的最优解：定义两个指针，即快慢指针，慢指针走一步的同时快指针走两步，直到快指针->next为空。这时慢指针指向的位置即为中间节点。

struct ListNode\* middleNode(struct ListNode\* head){
    if(head->next == NULL)
       return head;
    struct ListNode\* slow = head;
    struct ListNode\* fast = head;
    while(fast&&fast->next)//&&的特点，上一个不成立，下一个条件不判断，不会出现野指针的情况
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

1
2
3
4
5
6
7
8
9
10
11
12
13

3.4 删除链表的倒数第 N 个结点

19. 删除链表的倒数第 N 个结点

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

示例 1：

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

1
2
3

示例 2：

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

1
2
3

示例 3：

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

1
2
3

提示：

• 链表中结点的数目为 sz
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

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

思路： 这里我们仍然利用双指针的方法，即前后指针：通过观察不难发现，让前指针先走N步，再让后指针与前指针同时走，直到后指针为空，前指针就走到了倒数第N个节点，再让prev记录上一个节点的位置，从而进行连接。

struct ListNode\* removeNthFromEnd(struct ListNode\* head, int n){
    if(head == NULL)
        return head;
    if(head->next == NULL&&n==1)
        return NULL;
    struct ListNode\* cur = head;
    struct ListNode\* fast = head;
    struct ListNode\* slow = head;
    while(n--)
    {
        fast = fast->next;
    }
    struct ListNode\* prev = NULL;
    while(fast)
    {
        prev = slow;
        slow = slow->next;
        fast = fast->next;
    }
    if(prev == NULL)
    {
        head=head->next;

    }
    else
    {
        prev->next = slow->next;
    }
    return head;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

3.5 链表中倒数第k个节点

剑指 Offer 22. 链表中倒数第k个节点

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

示例：

给定一个链表: 1->2->3->4->5, 和 k = 2.

返回链表 4->5.

1
2
3
4

与上题寻找的思路一样，只不过不是删除，而是直接返回slow。需要注意k>链表长度，fast需要提前判空

struct ListNode\* getKthFromEnd(struct ListNode\* head, int k){
    if(head == NULL || k == 0)
        return NULL;
    struct ListNode\* fast = head;
    struct ListNode\* slow = head;
    while(k--)
    {
        if(fast == NULL)
            return NULL;
        else
            fast = fast->next;

    }
    while(fast)
    {
        fast = fast->next;
        slow = slow->next;
    }
    return slow;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

3.6 合并两个有序链表

21. 合并两个有序链表

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

示例 1：

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

1
2
3

示例 2：

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

1
2
3

示例 3：

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

1
2
3

提示：

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

思路： 采用归并的思想，新建一个头结点，两个链表节点依次比较，哪个小哪个连接，并将小的对应的链表向下一个节点。

struct ListNode\* mergeTwoLists(struct ListNode\* list1, struct ListNode\* list2){
    if(list1 == NULL)
        return list2;
    if(list2 == NULL)
        return list1;
    struct ListNode\* cur1 = list1;
    struct ListNode\* cur2 = list2;
    struct ListNode\* newHead = (struct ListNode\*)malloc(sizeof(struct ListNode));
    newHead->next = NULL;
    struct ListNode\* tail = newHead;
    while(cur1 && cur2)
    {
        if(cur1->val<cur2->val)
        {
            tail->next = cur1;
            cur1 = cur1->next;
        }
        else
        {
            tail->next = cur2;
            cur2 = cur2->next;
        }
        tail = tail->next;
    }
    if(cur1)
        tail->next = cur1;
    if(cur2)
        tail->next  =cur2;
    return newHead->next;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

3.7 分割链表

面试题 02.04. 分割链表

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

你需要 保留 每个分区中各节点的初始相对位置。（将题干改成了需要保留，原题为不需要保留）

示例 1：

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

1
2
3

示例 2：

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

1
2
3

提示：

• 链表中节点的数目在范围 [0, 200] 内
• -100 <= Node.val <= 100
• -200 <= x <= 200

思路：通过创建两个新的头节点（哨兵位）将此链表进行按照条件进行归类，并分别记录尾部，归类之后将两个链表进行连接，最后free掉两个节点

struct ListNode\* partition(struct ListNode\* head, int x){
    struct ListNode\* less = (struct ListNode\*)malloc(sizeof(struct ListNode));
    struct ListNode\* large = (struct ListNode\*)malloc(sizeof(struct ListNode));
    less->next=NULL;
    large->next=NULL;
    struct ListNode\* lesstail=less;
    struct ListNode\* largetail=large;
    struct ListNode\* cur=head;
    while(cur)
    {
        if(cur->val<x)
        {
            lesstail->next=cur;
            lesstail=lesstail->next;
        }
        else
        {
            largetail->next=cur;
            largetail=largetail->next;
        }
        cur=cur->next;
    }
    largetail->next=NULL;
    lesstail->next=large->next;
    head=less->next;
    free(less);
    free(large);
    large=less=NULL;
    return head;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

3.8 回文链表

234. 回文链表

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

示例 1：

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

1
2
3

示例 2：

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

1
2
3

提示：

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

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

解题步骤：对此，总结的一句话就是，不能重复造轮子（能偷懒就偷懒），我们可以利用上面的中间节点+反转链表进行操作：

即： 找到中间节点之后将前后分割开并对后半部分进行反转，对这两个链表节点的数据域的val进行一一对比，不管原本链表是奇数还是偶数长度，分割开即便是一奇一偶，判断时若有一个链表迭代到空（此时一奇一偶），即为回文链表，因为中间的数本来也只有一个。

注：即便分割成两个链表后不将前半部分的链表最后指向空，一样可以判断，因为前半部分最后指向的肯定是原本中间的那个，即后半链表反转之后的最后一个。此代码即为此。

//反转链表：
struct ListNode\* reverseList(struct ListNode\* head) {
    if (head == NULL || head->next == NULL)
        return head;
    struct ListNode\* prev = NULL, \* cur = head, \* next = head->next;
    while (cur)
    {
        //反转链表
        cur->next = prev;
        //迭代
        prev = cur;
        cur = next;
        if (next)
            next = next->next;
    }
    return prev;
}
//链表的中间节点：
struct ListNode\* middleNode(struct ListNode\* head){
    if(head->next == NULL)
        return head;
    struct ListNode\* slow = head;
    struct ListNode\* fast = head;
    while(fast&&fast->next)//&&的特点，上一个不成立，下一个条件不判断，不会出现野指针的情况
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}
bool isPalindrome(struct ListNode\* head){
    struct ListNode\* mid = middleNode(head);
    struct ListNode\* rmid = reverseList(mid);
    while(head && rmid)
    {
        if(head->val != rmid->val)
            return false;

        head = head->next;
        rmid = rmid->next;

    }
    return true;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

但这时会有小伙伴们想到，直接反转链表并将此链表与反转后的一一对比是不是也可以？答案是否定的，因为反转此链表之后，原本的链表内部同样会反转，相当于自己与自己比较，无论是不是回文结构，都会返回true,因此，若想用这个方法，必须在通过开辟节点或者用数组存储原本数据与其反转之后的进行比较，但不论是开辟新节点还是用数组，都是很挫的方式，若有别的方法解决，就不要用此方法。

3.9 相交链表

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
2
3
4
5
6

示例 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 个节点。

1
2
3
4
5
6

示例 3：

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

1
2
3
4
5
6

提示：

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

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

对于此题，直接想到的方法就是暴力求解，即每个节点都用一个完整的链表扫描，必然会扫描到（这种方式过于麻烦呜呜呜）。但，由于作者本着：没有优解，博客不写的原则，那么开始介绍优解的方法：

思路： 通过题干不难发现，由于不知道两个链表到相交位置的距离，我们无法利用两个指针去寻找，但是如果两个链表的起始位置到相交节点的距离相同，我们就可以用两个指针进行一起一步一步的前进，他们必然会相遇。可惜的是，两个链表的起始位置到相交节点的距离也不一定就相同呀，那么现在的问题就变成了如何让两个指针到交点的距离相同。

当我们从后往前看的时候，不难发现，两个链表的长度差1，并且，我们发现，若是让下面的链表的指针从b2开始扫描，那么就符合我们上述所提到的：距离相同 。这个时候，你一定会发觉并且猜想到，让长的链表先移动两个链表长度之差的长度 ，就可以让其并行，即到相交位置的距离相同。想到这里，这道题目，也就迎刃而解了。（恭喜恭喜）

经过一系列的揣测与分析加上有点蒙题的猜想，那就……可以上代码了：

struct ListNode \*getIntersectionNode(struct ListNode \*headA, struct ListNode \*headB) {
    if(headA == NULL ||headB == NULL)
        return NULL;

    struct ListNode\* curA = headA, \*curB = headB;
    int lenA = 1;
    //找尾节点
    while(curA)
    {
        curA = curA->next;
        ++lenA;
    }
    int lenB = 1;
    while(curB)
    {
        curB = curB->next;
        ++lenB;
    }
    struct ListNode\* longList = headA, \*shortList = headB;
    if(lenA<lenB)
    {
        longList = headB;
        shortList = headA;
    }
    //长的链表先走差距步
    int gap = abs(lenA-lenB);
    while(gap--)
    {
        longList = longList->next;
    }
    while(longList!=shortList)
    {
        longList = longList->next;
        shortList  = shortList->next;
    }
    return longList;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

那么对其进行相交与不相交的情况的归类，发现最后一个例子仅仅是一个链表也可以看成为相交链表（不禁让想象变得丰富起来）

4. 链表成环问题

对此，也有相应的oj题，但为什么还要单拿出来进行描述呢，由于这里的推导较多，为了让文章看着不混乱，选择给他一个大标题进行单独描述。

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

由于有扩展问题，我们先解决题目：

LeetCode.41. 环形链表

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

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

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

示例 1：

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

1
2
3
4

示例 2：

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

1
2
3
4

示例 3：

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

1
2
3
4

提示：

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

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

对于成环问题，如果是环，那么链表迭代的过程中不会截止，但是我们不能根据是否截止进行判断是不是环，这样只会运行超时，因此，需要采用一定的特殊技巧：

• 利用快慢指针，即快指针一次走两步，慢指针一次走一步，当慢指针进入环后，转化思想为快指针追赶慢指针：根据相对运动，每次移动快指针都会离慢指针更进一步，这就使得二者一定会在圈中相遇。即为真。
• 如果不是环，快指针一定先走到末端。

bool hasCycle(struct ListNode \*head) {
    if(head == NULL)
        return false;
    struct ListNode\* slow = head,\*fast = head;
    while(fast && fast->next)//一次走两步，防止出现野指针需要判断两个条件
    {
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast)
        {
            return true;
        }
    }
    return false;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

【扩展问题】

• 为什么快指针每次走两步，慢指针走一步可以？
  假设链表带环，两个指针最后都会进入环，快指针先进环，慢指针后进环。当慢指针刚进环时，可能就和快指针相遇了，最差情况下两个指针之间的距离刚好就是环的长度。此时，两个指针每移动一次，之间的距离就缩小一步，不会出现每次刚好是套圈的情况，因此：在满指针走到一圈之前，快指针肯定是可以追上慢指针的，即相遇。
  
• 快指针一次走3步行吗？
• • 不一定。慢指针在进圈后，快指针以相对慢指针两个单位两个单位的追赶，如果N为奇数（N代表两个指针之间的距离），距离就会变成：N-2,N-4,……3,1,-1。当变成-1时，又是一个新的开始，此时二者相距C-1个长度，C为环的周长，如果c-1是奇数，那么就永远不会相遇，因此不一定。
• 快指针一次走M步行吗？
• • 对此，可与一次走三步的类似，需要看N与C的关系。
• 慢指针一次走N步，快指针一次走M步行吗？（M>N)
• • 只要是在环中，并且M比N大1个单位，那么就可以认为快指针相对慢指针靠近一步，这样相当于遍历所有可能性，一定会相遇。

总结：只要fast比slow快一步，无论他们一次走几个单位，都一定可以相遇。

既有适合小白学习的零基础资料，也有适合3年以上经验的小伙伴深入学习提升的进阶课程，涵盖了95%以上大数据知识点，真正体系化！

由于文件比较多，这里只是将部分目录截图出来，全套包含大厂面经、学习笔记、源码讲义、实战项目、大纲路线、讲解视频，并且后续会持续更新

需要这份系统化资料的朋友，可以戳这里获取

针需要判断两个条件
{
slow = slow->next;
fast = fast->next->next;
if(slow == fast)
{
return true;
}
}
return false;
}

【扩展问题】



> 
> * 为什么快指针每次走两步，慢指针走一步可以？  
>  假设链表带环，两个指针最后都会进入环，快指针先进环，慢指针后进环。当慢指针刚进环时，可能就和快指针相遇了，最差情况下两个指针之间的距离刚好就是环的长度。此时，两个指针每移动一次，之间的距离就缩小一步，不会出现每次刚好是套圈的情况，因此：在满指针走到一圈之前，快指针肯定是可以追上慢指针的，即相遇。  
>  ![在这里插入图片描述](https://img-blog.csdnimg.cn/13f67cab8dd544cb8cf62594cda84447.png)
> * 快指针一次走3步行吗？
> * + 不一定。慢指针在进圈后，快指针以相对慢指针两个单位两个单位的追赶，如果N为奇数（N代表两个指针之间的距离），距离就会变成：N-2,N-4,……3,1,-1。当变成-1时，又是一个新的开始，此时二者相距C-1个长度，C为环的周长，如果c-1是奇数，那么就永远不会相遇，因此不一定。
> * 快指针一次走M步行吗？
> * + 对此，可与一次走三步的类似，需要看N与C的关系。
> * 慢指针一次走N步，快指针一次走M步行吗？（M>N)
> * + 只要是在环中，并且M比N大1个单位，那么就可以认为快指针相对慢指针靠近一步，这样相当于遍历所有可能性，一定会相遇。
> 
> 
> 


**总结：只要fast比slow快一步，无论他们一次走几个单位，都一定可以相遇。**



[外链图片转存中...(img-HbGgTMsG-1714673712285)]
[外链图片转存中...(img-voIRoOjq-1714673712286)]
[外链图片转存中...(img-JeGWhI4f-1714673712286)]

**既有适合小白学习的零基础资料，也有适合3年以上经验的小伙伴深入学习提升的进阶课程，涵盖了95%以上大数据知识点，真正体系化！**

**由于文件比较多，这里只是将部分目录截图出来，全套包含大厂面经、学习笔记、源码讲义、实战项目、大纲路线、讲解视频，并且后续会持续更新**

**[需要这份系统化资料的朋友，可以戳这里获取](https://bbs.csdn.net/topics/618545628)**

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34