单手杀穿经典链表题Pt.3——LeetCode天梯渡劫

目录

• • 传统艺能😎
  • 相交链表🤔
  • 环形链表🤔
  • 环形链表 II🤔
  • 复制带随机指针的链表🤔

传统艺能😎

小编是双非本科大一菜鸟不赘述，欢迎大佬指点江山（QQ：1319365055）
此前博客点我！点我！请搜索博主 【知晓天空之蓝】
乔乔的gitee代码库（打灰人 ）欢迎访问，点我！

🎉🎉非科班转码社区诚邀您入驻🎉🎉
小伙伴们，打码路上一路向北，背后烟火，彼岸之前皆是疾苦
一个人的单打独斗不如一群人的砥砺前行
这是我和梦想合伙人组建的社区，诚邀各位有志之士的加入！！
社区用户好文均加精（“标兵”文章字数2000+加精，“达人”文章字数1500+加精）
直达： 社区链接点我

你一定要走，走到灯火通明

——卢思浩《你要去相信，没有到不了的明天》

相交链表🤔

链接：相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
题目数据 保证 整个链式结构中不存在环。注意，函数返回结果后，链表必须 保持其原始结构 。如果程序能够正确返回相交节点，那么你的解决方案将被视作正确答案

示例:

输入：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 个节点。

思路：解题方法比较清奇，有点快慢指针内味，但并非快慢指针，我们要构筑相同路程，为什么？因为两个不等长的链表相交，指针走位不同步就无法比对内容。

只有两个链表不为空是才可能相交，那么链表最后尾节点内容和地址是必然相同的，所以我们重点是同步指针，让他们同时到达尾节点，链表 A 不重叠部分长度为 x，链表 B 不重叠部分长度为 y ，两链表重叠部分长度为 z，遍历两个链表时，A 变成 NULL就让指针指向链表 B 的头结点，B 变成 NULL就让指针指向链表 A 的头结点，抽象个图出来就是这样：

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     struct ListNode *next; * }; */struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {    struct ListNode *p1 = headA;    struct ListNode *p2 = headB;while(p1 != p2)    {if(p1==NULL){    p1 = headB;}else{    p1 = p1->next; }if(p2==NULL){    p2 =headA;}else{   p2 =p2->next; }    }    return p1;}

你学废了吗~

环形链表🤔

链接：环形链表

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

思路：有请我们的老朋友：快慢指针！！！
知不知道双指针的含金量啊铁咩！我们既然是环形链表就不怕走到头，只管去找就行了，快指针一次走两步，慢指针一次走一步，遍历的边界就是快指针遍历完两遍链表，这时候慢指针刚好遍历完一遍，如果快指针遇到了慢指针就说明有猫腻。

bool hasCycle(struct ListNode *head) {    struct ListNode *slow = head;    struct ListNode *fast = head;    while(fast && fast->next)    {slow = slow->next;fast = fast->next->next;if(slow==fast)return  true;    }return false;}

你学废了吗~

环形链表 II🤔

链接：环形链表 II

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，不允许修改 链表。

这道题是力扣的中等难度题，他奈奈滴，说的芥末复杂，其实就是在原来判读环形链表基础上多了步找到环形节点罢了。

struct ListNode *detectCycle(struct ListNode *head) {    struct ListNode *cur = head;    struct ListNode *tail = head;    while(tail && tail->next)    { cur = cur->next; tail = tail->next->next;//判断环形链表    if(cur == tail)    {    struct ListNode *head2 = tail;     struct ListNode *p1 = head2;     struct ListNode *p2 = head;    //   tail =NULL;     while(p1 != p2)     {  p1 = p1==NULL?head:p1->next;  p2 = p2==NULL?head2:p2->next;     }//同上上一题，构筑相同路程找到该节点     return p1;    }}return NULL;}

你学废了吗~

复制带随机指针的链表🤔

链接：复制带随机指针的链表

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和
random
指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有
x.random --> y 。 返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 val：一个表示 Node.val 的整数
random_index：随机指针指向的节点索引（范围从 0 到 n-1） 如果不指向任何节点，则为 null 。你的代码 只
接受原链表的头节点 head 作为传入参数。

示例：

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

思路：不开玩笑的说，这道题才配得上力扣给的中等难度，我读懂题目的时候已经老泪纵横了，再看看示例的图直接给我干破防了

思路：这道题本质就是一个深度拷贝，最大的难点就是如何处理所谓的随机指针，指向随机内容的指针到底该怎么去链接呢？就只有一个办法那就是顺藤摸瓜，从头节点一路向北，不就是复制这个链表吗，那我先创建一个一模一样的链表出来，但是这可不是简简单单复制出来就行，这还是个技术活诶，我们采用尾随式拷贝：

这种结构的好处就是可以跟进，在复制阶段可以靠拷贝节点的前一个节点（原节点）的随机指针来跟进到复制链表中找到拷贝节点的随机指针，从而达到深度拷贝的目的，逻辑结构就是拷贝节点指向的随机节点是拷贝节点前一个节点的随机指针指向的节点的下一个：

整个链表就构建完成了，要得到我们的成品就要将原来链表和拷贝链表分离，最后重组拷贝链表就行了。
总结一下就是三步走战略：

1. 原链表每个节点后复制这个节点，与原链表相连形成新链表；
2. 遍历链表，让 p->next->random = p->random->next ,以此完成链表的拷贝；
3. 将原链表和拷贝链表拆分，再重组出拷贝链表即可

struct Node* copyRandomList(struct Node* head) {    if(head==NULL)    { return NULL;    }    //新建拷贝链表    struct Node* cur = head;    while(cur)    { struct Node* new = (struct Node*)malloc(sizeof(struct Node)); new->val =  cur->val; new->next = cur->next;//与拷贝节点链接成新链表  cur->next = new; cur = cur->next->next;    }    cur = head;    //处理random指针    while(cur)    {struct Node* node = cur->next;if(cur->random == NULL){    node->random = NULL;}else{    node->random = cur->random->next;}cur = cur->next->next;    }    //重建链表(解下再链接)    cur = head;    struct Node* copyhead=NULL;    struct Node* copytail=NULL;    while(cur)    {    struct Node* copy = cur->next;    struct Node* next = copy->next;    cur->next = next;     if(copyhead==NULL)     {  copytail=copyhead=copy;     }     else     {copytail->next = copy;copytail = copytail->next;     }     cur =next;    }return copyhead;}

思路理解起来并不难，但是过程中很多细节需要自己去慢慢打磨，这是一个很不错的题目，如果你可以很顺利做出来，那么恭喜你，你对链表的理解已经满分了。

你学废了吗~

麦克风网