- 1离线数仓和实时数仓架构对比_实时数仓和离线数仓的区别
- 2耗时80小时！超详细的胎教级Stable Diffusion使用教程，看这一篇就够！_sd负面关键词模版
- 3latex 改变字体颜色_latex \color
- 4【A星算法】A星A*寻路算法详解（小白一看就懂+C#代码+零基础学习A*）
- 5利用ffmpeg截图工具截取视频关键帧
- 6农村商业银行与中国农业银行的区别
- 7linux查看网卡型号和驱动信息_linux查看网卡驱动
- 8mysql数据管理--外键&数据的增删改_sql有外键的怎么修改数据
- 93秒获得Win11系统管理员权限，微软高危漏洞被公开，只因悬赏奖金打骨折
- 10MySQL备份恢复之 xtrabackup增量备份_--incremental-basedir
【数据结构】链表相关OJ题 (万字详解)_数据结构oj题目
赞
踩
一、移除链表元素
题目链接
题目描述
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点。
解题思路
思路1
遍历链表，比对每一个节点的数据与val是否相等，如果相等，就free掉该节点。时间复杂度：O(N) 空间复杂度：O(1)
易错点
1、当链表的头结点的数据等于val时，我们free掉该节点后需要挪动head指针，让其指向新的头结点；
2、我们在遍历链表的时候需要记录前一个节点的地址，因为当我们free掉当前节点之后，我们要让前一个节点的next；链接到当前节点的下一个节点；
代码实现
//法一：遍历链表，找到等于val的节点就free掉 struct ListNode* removeElements(struct ListNode* head, int val){ struct ListNode* cur = head, *prev = NULL; while(cur) { if(cur->val == val) //移除 { if(cur == head) //头删，需要改变头结点 { head = cur->next; free(cur); cur = head; } else //非头删，正常移除 { prev->next = cur->next; free(cur); cur = prev->next; } } else //保留 { prev = cur; cur = cur->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
思路2
遍历链表，将不等于val的节点尾插到一个新的链表，将等于val的节点free掉。时间复杂度：O(N) 空间复杂度：O(1)
易错点
1、由于我们是把原链表中的节点尾插到新链表中去，所以我们插入元素的时候需要判断链表是否为空，如果为空，我们需要改变新链表的头结点；
2、当然，我们也可以把我们的新链表设计为带哨兵位的，这样我们直接进行尾插就行，但是要注意我们返回的应该是guard->next，因为哨兵位头结点不用于存储数据，同时在return之前记得把哨兵位头结点释放掉；
3、由于原链表中最后一个节点的数据可能等于val，所以我们需要将新链表中尾结点的next置为NULL，防止通过它来访问已经被释放掉的节点。
代码实现
//法二：取不等于val的节点尾插 struct ListNode* removeElements(struct ListNode* head, int val){ struct ListNode* guard = (struct ListNode*)malloc(sizeof(struct ListNode)); //哨兵位头结点 guard->next = NULL; //当原链表为空时我们可以正常返回 struct ListNode* tail = guard, *cur = head; while(cur) { if(cur->val == val) //移除 { struct ListNode* next = cur->next; free(cur); cur = next; } else //尾插 { tail->next = cur; tail = cur; cur = cur->next; } } tail->next = NULL; //避免当最后一个元素别移除时前面还保留它的地址，造成野指针 head = guard->next; free(guard); guard = 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
二、反转链表
题目链接
题目描述
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
思路分析
思路1
反转每一个节点的指向：定义三个节点指针prev cur next，最开始让prev指向NULL，cur指向head，next指向cur->next，然后让cur->next指向prev，最后进行迭代，即让prev=cur、cur=next、next=cur->next，直到cur为空时循环结束，此时prev为反转后的链表的头结点。时间复杂度：O(N) 空间复杂度：O(1)
易错点
1、我们需要定义一个next变量来保存下一个节点的地址，因为当我们让当前节点指向前一个节点时，我们会丢失下一个节点的地址；
2、当cur->next为NULL时，我们再将cur->next=prev，然后cur=next，此时所有节点反转完毕，cur==NULL，循环结束；
代码实现
//法一：让每一个节点指向它的前一个节点（三指针）
struct ListNode* reverseList(struct ListNode* head){
struct ListNode* prev = NULL, *cur = head, *next = NULL;
while(cur)
{
//翻转节点的指向
next = cur->next;
cur->next = prev;
//迭代
prev = cur;
cur = next;
}
return prev; //此时尾结点是新的头节点
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
思路2
将原链表中的节点头插到新链表中，然后返回新链表的头。时间复杂度：O(N) 空间复杂度：O(1)
易错点
如果我们的链表不带头，我们每头插一个元素都需要改变头结点。
代码实现
//法二：取出链表的每一个节点头插
struct ListNode* reverseList(struct ListNode* head){
struct ListNode* newhead = NULL;
struct ListNode* cur = head;
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
三、链表的中间节点
题目链接
题目描述
给定一个头结点为 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。时间复杂度：O(N) 空间复杂度：O(1)
思路分析
思路1
遍历两遍数组，第一遍求出链表长度，第二步找出链表的中间节点并返回。
代码实现
//法一：遍历两次链表，第一次找出链表有几个节点，第二次返回链表的中间节点 struct ListNode* middleNode(struct ListNode* head){ struct ListNode* cur = head; int count = 0; while(cur) { count++; cur = cur->next; } cur = head; count /= 2; while(count--) { cur = cur->next; } return cur; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
思路2
由于这道题用第一种方法实现十分简单，所以在面试中面试官会加一个限制条件：要求只能遍历一遍链表；这时候就只能用快慢指针来解题了；
快慢指针：定义两个指针 – fast slow，慢指针一次走一步，快指针一次走两步；当链表长度为奇数，fast->next == NULL时，slow 为中间节点；当链表长度为偶数，fast == NULL 时，slow 为中间节点。时间复杂度：O(N) 空间复杂度：O(1)
易错点
我们在写while循环的条件时，必须写成 fast && fast->next，不能写成 fast->next && fast，因为当链表长度为偶数时，后面这种写法会发生空指针的解引用。
代码实现
//法二：使用快慢指针，slow一次走一步，fast一次走两步，只遍历一遍数组
//奇数个节点时，当fast->next == NULL时，slow刚好到达中间节点
//偶数个节点时，当fast == NULL时，slow刚好达到中间节点
struct ListNode* middleNode(struct ListNode* head){
struct ListNode* fast, *slow;
slow = fast = head;
//注意：while条件中fast一定要写前面，不然偶数个时fast->next会造成空指针解引用
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
- 14
四、链表中倒数第K个节点
题目链接
链表中倒数第k个结点_牛客题霸_牛客网 (nowcoder.com)
题目描述
输入一个链表，输出该链表中倒数第k个结点。
思路分析
思路1也是遍历两遍链表，和上面题一样，这里我直接阐述思路2，思路2也是利用快慢指针的思想；O(N) 空间复杂度：O(1)
快慢指针：定义两个指针 – fast slow，先让 fast 走K/K-1步，然后让 fast 和 slow 一起走； fast 先走K步时，当 fast == NULL，slow 为倒数第K个元素；fast 先走K-1步时，当 fast->next == NULL，slow 为倒数第K个元素；这里与链表长度为奇数或者偶数无关。
易错点
注意：在做OJ类题目时，我们要考虑测试用例的边界情况，比如K等于1，K等于链表长度；还需要考虑测试用例的极端情况，比如链表为空，K为0，K大于链表长度；
在这道题中，我们正常编写的代码一般来说对于边界情况是能够正常通过的，对于极端情况中的NULL，K等于0也是能够通过的，但是K大于链表长度的情况很可能会被我们忽略；
当K大于链表长度时，如果我们 在K-- 的 while 循环中没有对 fast进 行空指针检查的话，那么 fast 会不断往后走，直到 fast == NULL 时仍然不会停下，这时候就会造成对空指针解引用的问题。
代码实现
//法二：快慢指针：让fast先走K/k-1步，然后slow和fast同时走，这时fast和slow之间就相差K/k-1个节点 //当fast先走K步时：fast == NULL //当fast先走K-1步时：fast->next == NULL struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) { // write code here struct ListNode* fast, *slow; fast = slow = pListHead; while(k--) //让fast先走K步 { if(fast == NULL) { return NULL; } 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
- 22
五、合并两个有序链表
题目链接
题目描述
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
思路分析
这道题的解题思路和顺序表中的合并两个有序数组的思路一模一样，只是这里尾插的是节点而已。时间复杂度：O(N) 空间复杂度：O(1)
易错点
1、由于我们是把原链表中的节点尾插到新链表中去，所以我们插入元素的时候需要判断链表是否为空，如果为空，我们需要改变新链表的头结点；
2、当然，我们也可以把我们的新链表设计为带哨兵位头的，这样我们直接进行尾插就行，但是要注意我们返回的应该是guard->next，因为哨兵位头结点不用于存储数据，同时在return之前我们要记得把哨兵位头结点释放掉；
代码实现
//取小的节点尾插 struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){ struct ListNode* guard = (struct ListNode*)malloc(sizeof(struct ListNode)); //哨兵位 guard->next = NULL; struct ListNode* tail = guard, *cur1 = list1, *cur2 = list2; while(cur1 && cur2) //取小的尾插 { if(cur1->val < cur2->val) { struct ListNode* next = cur1->next; tail->next = cur1; tail = cur1; //更新尾 cur1 = next; } else { struct ListNode* next = cur2->next; tail->next = cur2; tail = cur2; cur2 = next; } } //链接剩余的节点 if(cur1) tail->next = cur1; if(cur2) tail->next = cur2; struct ListNode* head = guard->next; free(guard); guard = 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
- 32
六、分隔链表
题目链接
面试题 02.04. 分割链表 - 力扣（LeetCode）
题目描述
分隔链表分为初阶版和进阶版，初阶版不要求我们保留每个分区中各节点的初始相对位置，而进阶版则要求要求我们保留每个分区中各节点的初始相对位置，这里我们讲解进阶版。
思路分析
思路1
取原链表中val小于x的节点节点头插，val大于x的节点尾插；此方法会改变链表中节点的初识相对位置，只适用于初阶。时间复杂度：O(N) 空间复杂度：O(1)
思路2
将原链表中val小于x的节点尾插到一个新链表中，将val大于x的节点尾插到另一个新链表中，最后将两个新链表链接起来。时间复杂度：O(N) 空间复杂度：O(1)
易错点
1、我们可以将两个新链表设计为带头链表，这样可以免去插入第一个元素时的判断步骤，避免犯错；
2、我们需要将用于链接val大于x的链表的尾结点的next置空，避免最后一个节点的val小于x时前一个节点的next仍指向它，从而形成环。
代码实现
//把大于等于X的节点和小于X的节点分别尾插到新的链表中，然后再把两个链表链接起来 struct ListNode* partition(struct ListNode* head, int x){ //开辟两个链表的头结点 struct ListNode* lessGuard = (struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode* greaterGuard = (struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode* lessTail = lessGuard, *greaterTail = greaterGuard, *cur = head; lessGuard->next = NULL; greaterGuard->next = NULL; while(cur) { if(cur->val < x) //如果小于X就尾插到less中 { lessTail->next = cur; lessTail = cur; } else //否则就尾插到greater中 { greaterTail->next = cur; greaterTail = cur; } cur = cur->next; } //让less的尾结点链接到greater的头结点 lessTail->next = greaterGuard->next; //把greater的头结点置空，防止当最后一个元素小于X被尾插到less时仍然指向它，从而形成环，造成死循环 greaterTail->next = NULL; head = lessGuard->next; //释放哨兵位头结点 free(greaterGuard); free(lessGuard); greaterGuard = NULL; lessGuard = 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
- 32
- 33
- 34
七、回文链表
题目链接
剑指 Offer II 027. 回文链表 - 力扣（LeetCode）
题目描述
给定一个链表的 头节点 head **，**请判断其是否为回文链表。如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。
思路分析
思路
找到链表的中间节点，将链表中间及以后的节点反转，然后用两个指针，一个指向链表开头，另一个指向反转部分的开头，遍历观察二者的val是否相等。时间复杂度：O(N) 空间复杂度：O(1)
易错点
我们反转的是中间及以后的节点，但是并未改变中间节点的前一个节点的next；也就是说，中间节点的前一个节点指向的是反转后的链表的最后一个节点；所以不管是链表长度是奇数还是偶数，我们都可以直接判断指针指向节点的val是否相等。
代码实现
//链表的中间节点 struct ListNode* middleNode(struct ListNode* head){ struct ListNode* fast, *slow; slow = fast = head; //注意：while条件中fast一定要写前面，不然偶数个时fast->next会造成空指针解引用 while(fast && fast->next) //节点是奇数还是偶数未知注意： { slow = slow->next; fast = fast->next->next; } return slow; } //反转链表 struct ListNode* reverseList(struct ListNode* head){ struct ListNode* newhead = NULL; struct ListNode* cur = head; while(cur) { struct ListNode* next = cur->next; cur->next = newhead; newhead = cur; cur = next; } return newhead; } //将链表的中间及以后的节点逆置，用两个指针分别指向头节点和中间节点，然后遍历链表看指针指向的节点的val是否相等 bool isPalindrome(struct ListNode* head){ //找到链表的中间节点 struct ListNode* mid = middleNode(head); //从链表的中间节点开始翻转链表 struct ListNode* reverse_mid = reverseList(mid); //遍历链表，看元素是否相等 struct ListNode* cur = head; while(cur && reverse_mid) { if(cur->val != reverse_mid->val) return false; cur = cur->next; reverse_mid = reverse_mid->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
八、相交链表
题目链接
题目描述
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
思路分析
从上面的例图我们可以知道：相交链表从相交的节点开始，后面的节点都是相同的，即相交链表的尾结点一定是相同的；所以我们可以先求出两个链表的长度，让较长的链表先走差距步；然后遍历两个链表，两个链表的节点地址相同处就是相交的起始节点。时间复杂度：O(N) 空间复杂度：O(1)
易错点
由于两个链表的长度不一定是相同的，所以我们不能直接对比两个链表的节点地址，这样会发生错位，而是应该先让两个链表对齐。
代码实现
//先让长度较长的链表向后走n步，让两个链表相等；然后开始遍历两个链表，找出地址相同的第一个节点，就是相交的起始节点 struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { struct ListNode* curA = headA, *curB = headB; int lenA = 1; int lenB = 1; if(curA == NULL || curB == NULL) //如果两个链表中有一个为空直接返回空 return NULL; //求出两个节点的长度 while(curA->next) { lenA++; curA = curA->next; } while(curB->next) { lenB++; curB = curB->next; } if(curA != curB) return NULL; //如果两个链表的尾结点的地址不同，则一定不相交；否则，就一定相交 //让长度较长的链表先走差距步 curA = headA; curB = headB; int k = abs(lenA - lenB); if(lenA > lenB) { while(k--) { curA = curA->next; } } else { while(k--) { curB = curB->next; } } //从cur位置处往后遍历链表，第一个相同地址的节点就是相交的起始节点 while(curA && curB) { if(curA == curB) return curA; curA = curA->next; curB = curB->next; } return NULL; //不加LeetCode不给过，但实际上不用加 }
- 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
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-9jbOMVLX-1659746535386)(C:/Users/yan/AppData/Roaming/Typora/typora-user-images/image-20220803223640749.png)]
九、环形链表
题目链接
题目描述
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
示例 1：
思路分析
快慢指针：定义两个指针 – fast 和 slow，快指针一次走两步，慢指针一次走一步，如果链表带环，二者最终会在链表的某个节点相遇。时间复杂度：O(N) 空间复杂度：O(1)
代码实现
//快慢指针：定义两个指针--fast和slow，fast一次走两步，slow一次走一步，如果链表有环，slow和fast最终会相等
bool hasCycle(struct ListNode *head) {
struct ListNode* fast = head, *slow = head;
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if(fast == slow) //如果快指针与慢指针相遇就代表有环
return true;
}
return false; //如果循环可以结束就代表没环
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
面试题（重点）
上面的代码十分简单，难点在于下面这几个面试题：
1、为什么快指针每次走两步，慢指针每次走一步，二者最终一定会在环中相遇？
2、快指针一次走三步，慢指针一次走一步，可不可以？
3、快指针一次走X步，慢指针一次走Y步可不可以？
实现我们先来解答第一个问题：
快指针每次走两步，慢指针每次走一步，所以当慢指针走到链表的中间节点时快指针刚好入环；
当慢指针入环时，快指针至少已经在环中走了一圈了：当链表的环比较大时，快指针可能只走了一圈多几步（最大的情况是链表的尾结点刚好链接到链表的头节点，此情况二者在头结点处相遇）；当链表的环比较小时，快指针可能在环中走了很多圈（最小的情况是链表的尾结点连接到尾结点，此情况二者在尾结点处相遇）；
总之：当慢指针入环时，慢指针和快指针直接的距离最小为0，最大为C-1（快指针在慢指针的前一个/后一个节点），其中C为环的长度；
而快指针一次走两步，慢指针一次走一步，二者之间的距离一次缩小1，所以快指针最坏走C-1步就能追上慢指针，二者相遇；所以快指针每次走两步，慢指针每次走一步，二者最终一定会在环中相遇。
然后我们来解答第二个问题：
有了上面的基础，后面的两个问题就比较简单了：快指针一次走三步，慢指针一次走两步，所以当慢指针走到链表的1/3处时快指针，入环；当慢指针入环时，快指针在环中走了k圈多n步（n步即是二者之间的距离）；
现在两个指针之间的距离为N，快指针一次走三步，慢指针一次走两步，二者之间的距离一次缩小2；所以这里就有两种情况：1、二者之间相差的步数n为偶数，这种情况下快指针在一圈内一定能够追上慢指针；
2、二者之间相差的步数n为奇数，这种情况下快指针和慢指针最后会相差一步，然后再往后走，快指针就会直接超过慢指针，而不会与慢指针相遇，这时候慢指针与快指针的距离又变为了C-1；这时又需要看环的长度，如果环的长度C为奇数，那么C-1为偶数，二者在这一圈内会相遇；如果C为偶数，那么C-1为奇数，二者就永远不会相遇了；
所以，当快指针一次走三步，慢指针一次走两步时，二者可能在环中相遇，也可能永远都不会相遇。
最后我们来总结第三个问题：
在解决了上面两个问题之后，第三问题的答案也就呼之欲出了：快指针一次走X步，慢指针一次走Y步，慢指针入环时二者的距离为N，快指针与慢指针之间的距离一次缩小X-Y，如果X-Y为1，则一定能够相遇；如果X-Y大于1，如2,3,4… … 可能相遇，也可能不相遇。
十、环形链表 II
题目链接
题目描述
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
思路分析
思路1
结论法：定义两个指针 – fast 和 slow，快指针一次走两步，慢指针一次走一步，首先求出二者在环中的相遇点；然后一个指针从链表的头开始走，另一个指针从相遇点开始走，最终二者会在入环点相遇。时间复杂度：O(N) 空间复杂度：O(1)
结论证明：我们假设环的长度为C，环之前的节点的长度为L，慢指针与快指针在环中X距离处相遇，相遇时快指针已经在环中走了N圈；则如下图所示：
代码实现
//法一：公式结论法--一个指针从链表的头开始走，另一个指针从相遇点开始走，二者最终会在入环点相遇 struct ListNode *detectCycle(struct ListNode *head) { struct ListNode* fast = head, *slow = head, *cur = head; while(fast && fast->next) { //迭代 slow = slow->next; fast = fast->next->next; //找到相遇的节点 if(fast == slow) { struct ListNode* meet = slow; //一个指针从头开始走，另一个指针从相遇点开始走 while(cur != meet) { cur = cur->next; meet = meet->next; } return cur; //二者最终会在入环点相遇 } } return NULL; //无环 }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
思路2
将链表求环问题转化为链表相交问题：定义两个指针 – fast 和 slow，快指针一次走两步，慢指针一次走一步，首先求出二者在环中的相遇点；然后记录下相遇点的下一个节点并让相遇点的next指向NULL；让相遇点的下一个节点作为新链表的头，与原链表求交点；最后再把相遇点的next复原。时间复杂度：O(N^2) 空间复杂度：O(1)
易错点
1、我们需要将相遇点的next置空，否则在求两个链表的交点的时候会发生死循环；
2、由于题目要求不修改原链表，所以最后我们需要把相遇点的next复原；
代码实现
//求两个链表的交点 //先让长度较长的链表向后走n步，让两个链表相等；然后开始遍历两个链表，找出地址相同的第一个节点，就是相交的起始节点 struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { struct ListNode* curA = headA, *curB = headB; int lenA = 1; int lenB = 1; if(curA == NULL || curB == NULL) //如果两个链表中有一个为空直接返回空 return NULL; //求出两个节点的长度 while(curA->next) { lenA++; curA = curA->next; } while(curB->next) { lenB++; curB = curB->next; } if(curA != curB) return NULL; //如果两个链表的尾结点的地址不同，则一定不相交；否则，就一定相交 //让长度较长的链表先走差距步 curA = headA; curB = headB; int k = abs(lenA - lenB); if(lenA > lenB) { while(k--) { curA = curA->next; } } else { while(k--) { curB = curB->next; } } //从cur位置处往后遍历链表，第一个相同地址的节点就是相交的起始节点 while(curA && curB) { if(curA == curB) return curA; curA = curA->next; curB = curB->next; } return NULL; //不加LeetCode不给过，但实际上不用加 } //法二：转换法--把环的入口问题转换为环的相交问题，即把链表从相遇点断开，一个指针从头开始走，一个指针从相遇点后面一个节点开始走，求二者相交 struct ListNode *detectCycle(struct ListNode *head) { struct ListNode* slow = head, *fast = head, *cur = head; while(fast && fast->next) { //迭代 slow = slow->next; fast = fast->next->next; //找到相遇点 if(slow == fast) { //记录相遇点的下一个节点，并把链表从相遇点断开，避免求相交的时候发生死循环 struct ListNode* meet = fast; struct ListNode* next = meet->next; meet->next = NULL; //求两个链表相交 struct ListNode* intersection = getIntersectionNode(cur, next); return intersection; //恢复原链表 meet->next = next; } } return NULL; //无环 }
- 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
十一、复制带随机指针的链表
题目链接
138. 复制带随机指针的链表 - 力扣（LeetCode）
题目描述
给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。
返回复制链表的头节点。
用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：
val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。
你的代码 只 接受原链表的头节点 head 作为传入参数。
思路分析
思路1
暴力求解：1、拷贝原链表的每个节点；2、得到原链表中每个节点的random指针指向的节点在链表中的相对位置；3、让新链表中每个节点的random指针指向处于相对位置的节点。时间复杂度：O(N^2) 空间复杂度：O(N)
代码实现
//拷贝节点 struct Node* CopyNode(struct Node* cur) { struct Node* copy = (struct Node*)malloc(sizeof(struct Node)); copy->next = NULL; copy->val = cur->val; copy->random = NULL; return copy; } //法一：1、拷贝原链表的每个节点；2、得到原链表中每个节点的random指针指向的节点在链表中的相对位置；3、让新链表中每个节点的random指针指向处于相对位置的节点 struct Node* copyRandomList(struct Node* head) { struct Node* cur = head; struct Node* newhead = NULL, *tail = NULL, *copy = NULL; //拷贝节点 while(cur) { //如果是复制第一个节点，需要改变头 if(tail == NULL) { copy = CopyNode(cur); newhead = tail = copy; } else { copy = CopyNode(cur); tail->next = copy; tail = tail->next; } //迭代 cur = cur->next; } //得到原链表中每个节点的random指针指向的节点在链表中的相对位置；并让新链表中每个节点的random指针指向处于相对位置的节点 cur = head; struct Node* copycur = newhead; while(cur && copycur) { int count = 0; struct Node* cur1 = head; //找到cur节点的random指针指向的节点在链表中的相对位置 while(cur->random != cur1) { count++; cur1 = cur1->next; } struct Node* copycur1 = newhead; //让copycur中每个节点的random指针指向处于相对位置的节点 while(count--) { copycur1 = copycur1->next; } copycur->random = copycur1; //迭代 cur = cur->next; copycur = copycur->next; } return newhead; }
- 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
思路2
1、将所有拷贝的节点链接到原节点的后面；2、将原节点的random指针指向节点的下一个节点赋给拷贝节点的random；3、将拷贝节点从原链表中分离出来，尾插到新链表中，并修复原链表中各节点的链接关系。时间复杂度：O(N) 空间复杂度：O(N)
易错点
1、由于我们是直接把拷贝节点链接到了原节点的后面，所以我们一定要注意链接关系的正确修改；并且迭代的时候我们需要让cur指向拷贝节点的下一个节点，即copy->next，而不是指向原节点的下一个节点，即cur->next；
2、在法一中，当原节点的random为NULL时，寻找相对位置的while循环会一直执行，直到cur1走到链表尾结点的下一个节点(NULL)，此时count为链表长度+1；然后新链表会把count处节点的地址(NULL)赋给对应节点的random，此时逻辑是正常的；
但是在法二中，当我们节点的random为NULL时，cur->random->next就会造成空指针解引用问题，所以这里我们需要对random为空的情况单独处理，需要特别注意，非常容易错；
3、由于我们在拷贝节点的时候就已经让尾结点的拷贝节点的next指向尾结点的next (NULL) 了，所以我们将拷贝节点插入到新链表中时不用特意将最后一个拷贝节点的next置空。
代码实现
//拷贝节点 struct Node* CopyNode(struct Node* cur) { struct Node* copy = (struct Node*)malloc(sizeof(struct Node)); copy->next = NULL; copy->val = cur->val; copy->random = NULL; return copy; } //法二：1、将所有拷贝的节点链接到原节点的后面；2、将原节点的random指针指向节点的下一个节点赋给拷贝节点的random；3、将拷贝节点从原链表中分离出来，尾插到新链表中，并修复原链表中各节点的链接关系 struct Node* copyRandomList(struct Node* head) { struct Node* cur = head, *copy = NULL, *next = NULL; struct Node* newhead = NULL, *tail = NULL; //1、将所有拷贝的节点链接到原节点的后面 while(cur) { //拷贝节点、修改链接关系 copy = CopyNode(cur); next = cur->next; cur->next = copy; copy->next = next; //迭代 cur = copy->next; } //2、将原节点的random指针指向节点的下一个节点赋给拷贝节点的random； cur = head; while(cur) { copy = cur->next; //原节点的random指针指向节点的下一个节点就是copy的random需要指向的节点 //这里需要判断cur的randon是否为空，为空就不能进行random->next操作 if(cur->random == NULL) copy->random = NULL; else { copy->random = cur->random->next; cur = copy->next; } //迭代 cur = copy->next; } //3、将拷贝节点从原链表中分离出来，尾插到新链表中，并修复原链表中各节点的链接关系 cur = head; while(cur) { copy = cur->next; //尾插第一个节点时，需要改变头 if(tail == NULL) { newhead = tail = copy; cur->next = copy->next; //修复原链表的链接关系 } else { tail->next = copy; tail = tail->next; cur->next = copy->next; } //迭代 cur = copy->next; } return newhead; }
- 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
