2023面试高手

这个屌丝很懒，什么也没留下！

热门标签

Leetcode学习之链表

作者：2023面试高手 | 2024-05-24 15:44:09

踩

Leetcode学习之链表

链表

1. 链表基础

什么是链表，链表是一种通过指针串联在一起的线性结构，每一个节点是又两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）。

链接的入口点称为列表的头结点也就是head。

如图所示：
在这里插入图片描述

1.1 链表类型

单链表
双链表

单链表中的节点只能指向节点的下一个节点。
双链表：每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。
双链表既可以向前查询也可以向后查询。

如图所示：

在这里插入图片描述
循环链表

循环链表，顾名思义，就是链表首尾相连。

循环链表可以用来解决约瑟夫环问题。

在这里插入图片描述

1.2 链表的存储方式

数组是在内存中是连续分布的，但是链表在内存中可不是连续分布的。

链表是通过指针域的指针链接在内存中各个节点。

所以链表中的节点在内存中不是连续分布的，而是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理。

如图所示：
在这里插入图片描述
这个链表起始节点为2，终止节点为7，各个节点分布在内存个不同地址空间上，通过指针串联在一起。

1.3 链表的定义

// 单链表
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) {}
};
1
2
3
4
5
6
7
8

通过自己定义构造函数初始化节点：

ListNode* head = new ListNode(5);
1

使用默认构造函数初始化节点：

ListNode* head = new ListNode();
head->val = 5;
1
2

2.链表的操作

2.1 删除节点

删除D节点，如图所示：
在这里插入图片描述
只要将C节点的next指针指向E节点就可以了。

那有同学说了，D节点不是依然存留在内存里么？只不过是没有在这个链表里而已。

是这样的，所以在C++里最好是再手动释放这个D节点，释放这块内存。

其他语言例如Java、Python，就有自己的内存回收机制，就不用自己手动释放了。

2.2 添加节点

如图所示：
在这里插入图片描述
可以看出链表的增添和删除都是 $O(1)$ 操作，也不会影响到其他节点。

但是要注意，要是删除第五个节点，需要从头节点查找到第四个节点通过next指针进行删除操作，查找的时间复杂度是 $O(n)$ 。

2.3 性能分析

	插入/删除（时间复杂度）	查询（时间复杂度）	适用场景
数组	$O (n)$	$O (1)$	数据量固定，频繁查询，较少增删
链表	$O (1)$	$O (n)$	数据量不固定，频繁增删，较少查询

数组在定义的时候，长度就是固定的，如果想改动数组的长度，就需要重新定义一个新的数组。

链表的长度可以是不固定的，并且可以动态增删，适合数据量不固定，频繁增删，较少查询的场景。

3. 移除链表元素

题目链接
题意：删除链表中等于给定值 val 的所有节点。

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

示例 2：
输入：head = [], val = 1
输出：[]

示例 3：
输入：head = [7,7,7,7], val = 7
输出：[]

3.1 思路

这里以链表 1 4 2 4 来举例，移除元素4。
在这里插入图片描述
如果使用C，C++编程语言的话，不要忘了还要从内存中删除这两个移除的节点，清理节点内存之后如图：

当然如果使用java ，python的话就不用手动管理内存了。

还要说明一下，就算使用C++来做leetcode，如果移除一个节点之后，没有手动在内存中删除这个节点，leetcode依然也是可以通过的，只不过，内存使用的空间大一些而已，但建议依然要养生手动清理内存的习惯。

这种情况下的移除操作，就是让节点next指针直接指向下下一个节点就可以了，

那么因为单链表的特殊性，只能指向下一个节点，刚刚删除的是链表的中第二个，和第四个节点，那么如果删除的是头结点又该怎么办呢？

这里就涉及如下链表操作的两种方式：

直接使用原来的链表来进行删除操作。
设置一个虚拟头结点在进行删除操作。

来看第一种操作：直接使用原来的链表来进行移除。

在这里插入图片描述
移除头结点和移除其他节点的操作是不一样的，因为链表的其他节点都是通过前一个节点来移除当前节点，而头结点没有前一个节点。

所以头结点如何移除呢，其实只要将头结点向后移动一位就可以，这样就从链表中移除了一个头结点。

在这里插入图片描述
依然别忘将原头结点从内存中删掉。
这样移除了一个头结点，是不是发现，在单链表中移除头结点和移除其他节点的操作方式是不一样，其实在写代码的时候也会发现，需要单独写一段逻辑来处理移除头结点的情况。

那么可不可以以一种统一的逻辑来移除链表的节点呢。

其实可以设置一个虚拟头结点，这样原链表的所有节点就都可以按照统一的方式进行移除了。

来看看如何设置一个虚拟头。依然还是在这个链表中，移除元素1。

在这里插入图片描述
这里来给链表添加一个虚拟头结点为新的头结点，此时要移除这个旧头结点元素1。

这样是不是就可以使用和移除链表其他节点的方式统一了呢？

来看一下，如何移除元素1 呢，还是熟悉的方式，然后从内存中删除元素1。

最后呢在题目中，return 头结点的时候，别忘了 return dummyNode->next;，这才是新的头结点

3.2 代码实现

/**
 * 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* removeElements(ListNode* head, int val) {
    	//增加虚拟头结点，不适用new,函数执行完自动释放，返回下一个结点即可
        ListNode dummy = ListNode(0, head);
        ListNode* pNode = &dummy;
        
        while (pNode->next != nullptr){
            if (pNode->next->val == val){
                ListNode* deleNote = pNode->next;
                pNode->next = pNode->next->next;
                delete deleNote;
            }
            else
                pNode = pNode->next;
        }
        return dummy.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

4. 设计链表

题目链接
题意：

在链表类中实现这些功能：

get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。

4.1 代码实现

单链表

#include <iostream>
using namespace std;

class MyLinkedList {
public:
	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){}
	};

    MyLinkedList() {
		_dummyHead = new ListNode(0);
		_size = 0;
    }
    
    int get(int index) {
		if (index < 0 || index >(_size - 1))
			return -1;

		ListNode* pNode = _dummyHead->next;
		while (index--)
			pNode = pNode->next;

		return pNode->val;
    }
    
    void addAtHead(int val) {
		if (_size == 0)
			_dummyHead->next = new ListNode(val);
		else{
			ListNode* pNode = _dummyHead->next;
			_dummyHead->next = new ListNode(val);
			_dummyHead->next->next = pNode;
		}
		
		_size++;
    }
    
    void addAtTail(int val) {
		ListNode* pNode = _dummyHead;
		ListNode* newNode = new ListNode(val);
		while (pNode->next != nullptr)
			pNode = pNode->next;

		pNode->next = newNode;
		_size++;
    }
    
    void addAtIndex(int index, int val) {
		if (index < 0)
			addAtHead(val);
		else if (index == _size)
			addAtTail(val);
		else if (index > _size)
			;
		else{
			ListNode* pNode = _dummyHead;
			while (index--)
				pNode = pNode->next;

			ListNode* Node = pNode->next;
			pNode->next = new ListNode(val);
			pNode->next->next = Node;
			_size++;
		}
    }
    
    void deleteAtIndex(int index) {
		if (index >= 0 && index < _size){
			ListNode* pNode = _dummyHead;
			while (index--)
				pNode = pNode->next;

			ListNode* deleNode = pNode->next;
			pNode->next = pNode->next->next;
			delete deleNode;
			deleNode = nullptr;
			_size--;
		}
    }

private:
	int _size;
	ListNode* _dummyHead;
};

void test01()
{
	MyLinkedList* linkedList = new MyLinkedList();
	linkedList->addAtHead(1);
	cout << "第一次增加：" << endl;
	cout << linkedList->get(0) << endl;
	linkedList->addAtTail(3);
	cout << "第二次增加：" << endl;
	cout << linkedList->get(0) << endl;
	cout << linkedList->get(1) << endl;

	linkedList->addAtIndex(1, 2);   //链表变为1-> 2-> 3
	cout << "第三次增加：" << endl;
	cout << linkedList->get(0) << endl;     //返回2
	cout << linkedList->get(1) << endl;     //返回2
	cout << linkedList->get(2) << endl;     //返回2
	linkedList->deleteAtIndex(1);  //现在链表是1-> 3
	cout << "第四次增加：" << endl;
	cout << linkedList->get(1) << endl;            //返回3
}
int main(){
	test01();
	system("pause");
	return 0;
}
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114

双链表

#include<iostream>
using namespace std;

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

class MyLinkedList{
public:
	MyLinkedList() {
		_head = new ListNode(0);
		_tail = new ListNode(0);
		_size = 0;
		_head->next = _tail;
		_tail->prev = _head;
	}

	int get(int index) {
		if (index < 0 || index >(_size - 1))
			return -1;

		ListNode* pNode = _head->next;
		while (index--)
			pNode = pNode->next;
		return pNode->val;
	}

	void addAtHead(int val) {
		ListNode* newNode = new ListNode(val, _head, _head->next);
		_head->next->prev = newNode;
		_head->next = newNode;
		_size++;
	}

	void addAtTail(int val) {
		ListNode* newNode = new ListNode(val, _tail->prev, _tail);
		_tail->prev->next = newNode;
		_tail->prev = newNode;
		_size++;
	}

	void addAtIndex(int index, int val) {
		if (index < 0)
			addAtHead(val);
		else if (index == _size)
			addAtTail(val);
		else if (index > _size)
			;
		else{
			ListNode* pNode = _head;
			while (index--)
				pNode = pNode->next;
			ListNode* newNode = new ListNode(val, pNode, pNode->next);
			pNode->next->prev = newNode;
			pNode->next = newNode;
			_size++;
		}
	}

	void deleteAtIndex(int index) {
		if (index >= 0 && index <= (_size - 1)){
			ListNode* pNode = _head;
			while (index--)
				pNode = pNode->next;

			ListNode* deleNode = pNode->next;
			pNode->next = pNode->next->next;
			pNode->next->prev = pNode;
			delete deleNode;
			_size--;
		}
	}

private:
	int _size;
	ListNode* _head;
	ListNode* _tail;
};

void test01(){
	MyLinkedList* linkedList = new MyLinkedList();
	linkedList->addAtHead(7);
	cout << "第一次增加：" << endl;
	cout << linkedList->get(0) << endl;
	cout << linkedList->get(1) << endl;

	linkedList->addAtTail(2);
	cout << "第二次增加：" << endl;
	cout << linkedList->get(0) << endl;
	cout << linkedList->get(1) << endl;
	cout << linkedList->get(2) << endl;

	linkedList->addAtHead(1);
	cout << "第三次增加：" << endl;
	cout << linkedList->get(0) << endl;
	cout << linkedList->get(1) << endl;
	cout << linkedList->get(2) << endl;
	cout << linkedList->get(3) << endl;

	linkedList->addAtIndex(0, 0);   
	cout << "第四次增加：" << endl;
	cout << linkedList->get(0) << endl;     
	cout << linkedList->get(1) << endl;     
	cout << linkedList->get(2) << endl;     
	cout << linkedList->get(3) << endl;
	cout << linkedList->get(4) << endl;     

	linkedList->deleteAtIndex(2);  
	cout << "第一次删除：" << endl;
	cout << linkedList->get(0) << endl;     
	cout << linkedList->get(1) << endl;     
	cout << linkedList->get(2) << endl;     
	cout << linkedList->get(3) << endl;    

	linkedList->addAtHead(6);
	cout << "第五次增加：" << endl;
	cout << linkedList->get(0) << endl;
	cout << linkedList->get(1) << endl;
	cout << linkedList->get(2) << endl;
	cout << linkedList->get(3) << endl;   
	cout << linkedList->get(4) << endl;  

	linkedList->addAtTail(6);
	cout << "第六次增加：" << endl;
	cout << linkedList->get(0) << endl;
	cout << linkedList->get(1) << endl;
	cout << linkedList->get(2) << endl;
	cout << linkedList->get(3) << endl;
	cout << linkedList->get(4) << endl;
	cout << linkedList->get(5) << endl;

}

int main()
{
	test01();

	system("pause");
	return 0;
}
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146

5. 反转链表

题目链接

题意：反转一个单链表。

示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL

5.1 思路

如果再定义一个新的链表，实现链表元素的反转，其实这是对内存空间的浪费。

其实只需要改变链表的next指针的指向，直接将链表反转，而不用重新定义一个新的链表，如图所示:
在这里插入图片描述

之前链表的头节点是元素1，反转之后头结点就是元素5 ，这里并没有添加或者删除节点，仅仅是改表next指针的方向。

我们拿有示例中的链表来举例，如动画所示：

在这里插入图片描述

首先定义一个cur指针，指向头结点，再定义一个pre指针，初始化为null。

然后就要开始反转了，首先要把 cur->next 节点用tmp指针保存一下，也就是保存一下这个节点。

为什么要保存一下这个节点呢，因为接下来要改变 cur->next 的指向了，将cur->next 指向pre ，此时已经反转了第一个节点了。

接下来，就是循环走如下代码逻辑了，继续移动pre和cur指针。

最后，cur 指针已经指向了null，循环结束，链表也反转完毕了。此时我们return pre指针就可以了，pre指针就指向了新的头结点。

5.2 双指针法代码实现：

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* reverseList(ListNode* head){
		ListNode* prev = nullptr;
		ListNode* curr = head;
		while (curr){
			ListNode* Node = curr->next;
			curr->next = prev;
			prev = curr;
			curr = Node;
		}
		return prev;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

6 两两交换链表中的节点

题目链接

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

在这里插入图片描述

6.1 思路

建议使用虚拟头结点，这样会方便很多，要不然每次针对头结点（没有前一个指针指向头结点），还要单独处理。

接下来就是交换相邻两个元素了，此时一定要画图，不画图，操作多个指针很容易乱，而且要操作的先后顺序

初始时，cur指向虚拟头结点，然后进行如下三步：

在这里插入图片描述
操作之后，链表如下：

看这个可能就更直观一些了：

进一步，将指针移动两步，判断是否进行交换，如果是，重复步骤，否则，工作完成。

6.2 代码实现

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* swapParis(ListNode* head){
		ListNode dummy = ListNode(0, head);
		ListNode* pNode = &dummy;
		while (pNode->next && pNode->next->next) {
			ListNode* swapNode = pNode->next; //原第一个指针
			pNode->next = pNode->next->next;  //将原第二个指针变为新第一个指针
			swapNode->next = pNode->next->next; //将新第二个指针指向第三个指针
			pNode->next->next = swapNode; //将新第一个指针指向第二个指针

			pNode = pNode->next->next; // 更新指针位置
		}
		return dummy.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

7. 删除链表的倒数第N个节点

题目链接

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

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

在这里插入图片描述
输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5] 示例 2：

输入：head = [1], n = 1 输出：[] 示例 3：

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

7.1 思路

双指针的经典应用，如果要删除倒数第n个节点，让fast移动n步，然后让fast和slow同时移动，直到fast指向链表末尾。删掉slow所指向的节点就可以了。

思路是这样的，但要注意一些细节。

分为如下几步：

首先这里我推荐大家使用虚拟头结点，这样方面处理删除实际头结点的逻辑。
定义fast指针和slow指针，初始值为虚拟头结点，如图：
fast首先走n + 1步，为什么是n+1呢，因为只有这样同时移动的时候slow才能指向删除节点的上一个节点（方便做删除操作），如图：
fast和slow同时移动，之道fast指向末尾，如题：

*删除slow指向的下一个节点，如图：

7.2 代码

注：上述思路是考虑让fast多走一步来推迟slow慢一步，方便删除，代码中，我喜欢让fast直接指向head，这样与找倒数第几个链表达成一致，方便学习！！！也推荐大家这样！！！

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(nullptr){}
};

class Solution{
public:
	ListNode dummy = ListNode(0, head); // 定义普通类，函数自动释放
	ListNode* pNode = &dummy;

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

	//删除倒数N个链表
	ListNode* deleNode = slow->next;
	slow->next = slow->next->next;
	delete deleNode
};
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

8. 链表相交

题目链接

给定两个（单向）链表，判定它们是否相交并返回交点。请注意相交的定义基于节点的引用，而不是基于节点的值。换句话说，如果一个链表的第k个节点与另一个链表的第j个节点是同一节点（引用完全相同），则这两个链表相交。

示例 1：

输入：listA = [4,1,8,4,5], listB = [5,0,1,8,4,5]

输出：Reference of the node with value = 8

输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

8.1 思路

本来很简洁明了的一道题，让题目描述搞的云里雾里的。

简单来说，就是求两个链表交点节点的指针。这里同学们要注意，交点不是数值相等，而是指针相等。

为了方便举例，假设节点元素数值相等，则节点指针相等。

看如下两个链表，目前curA指向链表A的头结点，curB指向链表B的头结点：

在这里插入图片描述
我们求出两个链表的长度，并求出两个链表长度的差值，然后让curA移动到，和curB 末尾对齐的位置，如图：

在这里插入图片描述
此时我们就可以比较curA和curB是否相同，如果不相同，同时向后移动curA和curB，如果遇到curA == curB，则找到焦点。

否则循环退出返回空指针。

另外一种方法，考虑双指针，我们让两个指针分别同时从A开始，从B开始，如果A指针走完了，没有和B指针找到相同的指针，不用着急，让A指针走B指针的路，这样，在B指针走完的时候，让B指针去走A指针的路，就把相交的前部分误差给抵消了，如果有相交部分，必定将在c1处会相交，可以自己在纸上画画图，然后两个手指头做做试验，就会明白。
在这里插入图片描述

8.2 代码实现

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* getIntersectionNode(ListNode* headA, ListNode* headB){
		ListNode* pNode1 = headA;
		ListNode* pNode2 = headB;
		//pNode1 不等于pNode2 会循环，如果两者没有相交的部分，则在循环完pNode1 和 pNode2后指针会同时变为nullptr, while循环停止。
		while (pNode1 != pNode2){
			pNode1 = pNode1 == nullptr? headB: pNode1->next;
			pNode2 = pNode2 == nullptr? headA: pNode2->next;
		}
		return pNode1;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

9. 环形链表II

题目链接
题意：给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

为了表示给定链表中的环，使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。

说明：不允许修改给定的链表。
在这里插入图片描述

9.1 思路

这道题目，不仅考察对链表的操作，而且还需要一些数学运算。

主要考察两知识点：

判断链表是否环
如果有环，如何找到这个环的入口

判断链表是否有环
可以使用快慢指针法，分别定义 fast 和 slow指针，从头结点出发，fast指针每次移动两个节点，slow指针每次移动一个节点，如果 fast 和 slow指针在途中相遇，说明这个链表有环。

为什么fast 走两个节点，slow走一个节点，有环的话，一定会在环内相遇呢，而不是永远的错开呢

首先第一点： fast指针一定先进入环中，如果fast 指针和slow指针相遇的话，一定是在环中相遇，这是毋庸置疑的。

那么来看一下，为什么fast指针和slow指针一定会相遇呢？

可以画一个环，然后让 fast指针在任意一个节点开始追赶slow指针。

会发现最终都是这种情况，如下图：

在这里插入图片描述
fast和slow各自再走一步， fast和slow就相遇了

这是因为fast是走两步，slow是走一步，其实相对于slow来说，fast是一个节点一个节点的靠近slow的，所以fast一定可以和slow重合。

动画如下：
在这里插入图片描述
如果有环，如何找到这个环的入口

假设从头结点到环形入口节点的节点数为x。环形入口节点到 fast指针与slow指针相遇节点节点数为y。从相遇节点再到环形入口节点节点数为 z。如图所示：

在这里插入图片描述
那么相遇时： slow指针走过的节点数为: x + y， fast指针走过的节点数：x + y + n (y + z)，n为fast指针在环内走了n圈才遇到slow指针， （y+z）为一圈内节点的个数A。

因为fast指针是一步走两个节点，slow指针一步走一个节点，所以 fast指针走过的节点数 = slow指针走过的节点数 * 2：
(x + y) * 2 = x + y + n (y + z)
两边消掉一个（x+y）: x + y = n (y + z)

因为要找环形的入口，那么要求的是x，因为x表示头结点到环形入口节点的的距离。

所以要求x ，将x单独放在左面：x = n (y + z) - y ,

再从n(y+z)中提出一个（y+z）来，整理公式之后为如下公式：x = (n - 1) (y + z) + z 注意这里n一定是大于等于1的，因为 fast指针至少要多走一圈才能相遇slow指针。

这个公式说明什么呢？

先拿n为1的情况来举例，意味着fast指针在环形里转了一圈之后，就遇到了 slow指针了。

当 n为1的时候，公式就化解为 x = z，

这就意味着，从头结点出发一个指针，从相遇节点也出发一个指针，这两个指针每次只走一个节点，那么当这两个指针相遇的时候就是环形入口的节点。

也就是在相遇节点处，定义一个指针index1，在头结点处定一个指针index2。

让index1和index2同时移动，每次移动一个节点，那么他们相遇的地方就是环形入口的节点。

动画如下：
在这里插入图片描述
上述步骤略啰嗦，看下方解释：
简单的说，slow为一步一步走的指针，fast为两步两步走的指针。如果环存在，slow指针走k步，fast指针走2k步，那么走一圈必为k步，假设从环的起点到第一次相遇的交点距离为m，当第一相交后，slow指针从头开始，走到环的起点为k-m，此时，fast指针也改为一步一步走，恰好走k-m步到达环首，可见，第一次相遇后，k-m再次相遇。

9.2 代码实现

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){
		ListNode* slow = head;
		ListNode* fast = head;

		while (fast != nullptr && fast->next != nullptr){
			fast = fast->next->next;
			slow = slow->next;
			if (fast == slow) break;
		}
		if (fast == nullptr || fast->next == nullptr) return NULL;
		slow = head;
		while (slow != 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
22
23
24
25
26
27
28

总结

链表的理论基础

链表的种类主要为：单链表，双链表，循环链表
链表的存储方式：链表的节点在内存中是分散存储的，通过指针连在一起。
链表是如何进行增删改查的。
数组和链表在不同场景下的性能分析。

可以说把链表基础的知识都概括了，但又不像教科书那样的繁琐。

链表经典题目

虚拟头结点

每次对应头结点的情况都要单独处理，所以使用虚拟头结点的技巧，就可以解决这个问题。

链表的基本操作

这是练习链表基础操作的非常好的一道题目，考察了：

获取链表第index个节点的数值
在链表的最前面插入一个节点
在链表的最后面插入一个节点
在链表第index个节点前面插入一个节点
删除链表的第index个节点的数值
可以说把这道题目做了，链表基本操作就OK了，再也不用担心链表增删改查整不明白了。

反转链表

因为反转链表的代码相对简单，有的同学可能直接背下来了，但一写还是容易出问题。

反转链表是面试中高频题目，很考察面试者对链表操作的熟练程度。

删除倒数第N个节点

见上

链表相交

见上

环形链表

见上

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/2023面试高手/article/detail/618084

Leetcode学习之链表

链表学习内容

链表

1. 链表基础

1.1 链表类型

1.2 链表的存储方式

1.3 链表的定义

2.链表的操作

2.1 删除节点

2.2 添加节点

2.3 性能分析

3. 移除链表元素

3.1 思路

3.2 代码实现

4. 设计链表

4.1 代码实现

5. 反转链表

5.1 思路

5.2 双指针法代码实现：

6 两两交换链表中的节点

6.1 思路

6.2 代码实现

7. 删除链表的倒数第N个节点

7.1 思路

7.2 代码

8. 链表相交

8.1 思路

8.2 代码实现

9. 环形链表II

9.1 思路

9.2 代码实现

总结

链表的理论基础

链表经典题目

虚拟头结点

链表的基本操作

反转链表

删除倒数第N个节点

链表相交

环形链表