【LeetCode&数据结构】单链表的应用——随机链表的复制问题、相交链表问题详解_链表复制

🔥个人主页：艾莉丝努力练剑

❄专栏传送门：《C语言》、《数据结构与算法》、C语言刷题12天IO强训、LeetCode代码强化刷题

🍉学习方向：C/C++方向

⭐️人生格言：为天地立心，为生民立命，为往圣继绝学，为万世开太平

前言：牛客网和LeetCode的刷题都不可或缺，我们都要做一做，无论是参加竞赛还是笔试面试，至少能提升你的代码能力！洛谷的题目也可以去做一做。力扣的题目对提升代码能力很有帮助，需要有一点基础，几乎都是接口型的题目，关于接口型和IO型的区别我们在本专栏的第一篇【LeetCode】力扣题——轮转数组、消失的数字、数组串联中就介绍过了，这里不再赘述，我们进入今天的力扣题目介绍——

目录

正文 

一、随机链表的复制问题

1、思路

（1）深拷贝

（2）浅拷贝：值拷贝

（3）深拷贝和浅拷贝的关系

2、解题过程

3、改进方案

（1）在原链表基础上拷贝节点

（2）置random指针

（3）断开新旧链表

 4、代码演示：

二、相交链表问题

 1、思路

2、解题过程

结尾

正文 

一、随机链表的复制问题

138.随机链表复制

博主题解链接：原链表基础上拷贝节点、置random指针、断开新旧链表解决随机链表的复制

推荐大家可以直接去看博主在力扣上面写的题解，博主介绍的还是比较详细的。

题目描述： 

题目示例和提示—— 

1、思路

我们的思路是：原链表基础上拷贝节点、置random指针、断开新旧链表。

我们先来看看题目描述——

题目提到了深拷贝，什么是深拷贝？

（1）深拷贝

如图——

（2）浅拷贝：值拷贝

如图——

（3）深拷贝和浅拷贝的关系

2、解题过程

像这种题目拿到手我们首先就是想到要画图，一定要有这个意识，数据结构的算法题一定要画图。

如下图所示—— 

random如何设置？ 

至于为什么不这么做的理由我已经在图中标注了。

3、改进方案

我们如果创建新链表再设置random指针，不太好去改变，所以我们可以三步走：

（1）在原链表基础上拷贝节点

（2）置random指针

（3）断开新旧链表

变成这样—— 

这里我们通过示例1看看，random表示从0开始的下标——

我们测试一下，代码演示——

/** * Definition for a Node. * struct Node { * int val; * struct Node *next; * struct Node *random; * }; */typedef struct Node Node;Node* buyNode(int x) {Node* newnode = (Node*)malloc(sizeof(Node)); newnode->val = x; newnode->next = newnode->random = NULL; return newnode;}void AddNode(Node* head){ Node* pcur = head; while(pcur) { Node* newnode = buyNode(pcur->val); Node* next = pcur->next; newnode->next = next; pcur->next = newnode; pcur = next; }}void setRandom(Node* head){ Node* pcur = head; while(pcur) { Node* copy = pcur->next; if(pcur->random) copy->random = pcur->random->next; pcur = copy->next; }}struct Node* copyRandomList(struct Node* head){ //在原链表基础上拷贝节点并且插入在原链表中 AddNode(head); //设置random setRandom(head); //断开新链表 Node* pcur = head; Node* copyHead,*copyTail; copyHead = copyTail = pcur->next; while(copyTail->next) { pcur = copyTail->next; copyTail->next = pcur->next; copyTail = copyTail->next; } return copyHead;}

 运行一下——报错了！

我们判断一下头节点是否为空，是就直接返回head——

 4、代码演示：

/** * Definition for a Node. * struct Node { * int val; * struct Node *next; * struct Node *random; * }; */typedef struct Node Node;Node* buyNode(int x) {Node* newnode = (Node*)malloc(sizeof(Node)); newnode->val = x; newnode->next = newnode->random = NULL; return newnode;}void AddNode(Node* head){ Node* pcur = head; while(pcur) { Node* newnode = buyNode(pcur->val); Node* next = pcur->next; newnode->next = next; pcur->next = newnode; pcur = next; }}void setRandom(Node* head){ Node* pcur = head; while(pcur) { Node* copy = pcur->next; if(pcur->random) copy->random = pcur->random->next; pcur = copy->next; }}struct Node* copyRandomList(struct Node* head){ if(head == NULL) { return head; } //在原链表基础上拷贝节点并且插入在原链表中 AddNode(head); //设置random setRandom(head); //断开新链表 Node* pcur = head; Node* copyHead,*copyTail; copyHead = copyTail = pcur->next; while(copyTail->next) { pcur = copyTail->next; copyTail->next = pcur->next; copyTail = copyTail->next; } return copyHead;}

复杂度：时间复杂度：O(N)，空间复杂度：O(1)。

运行一下，通过了。 

二、相交链表问题

160.相交链表

博主题解链接：利用长度差求解相交链表

推荐大家可以直接去看博主在力扣上面写的题解，博主介绍的还是比较详细的。

题目描述：

我们来看题目给的几个示例——

本题也给了一个提示——

 1、思路

从链表的长度我们可以联想到A和B存在长度差。

因此我们的思路是：求两个链表的长度，先让长链表走长度差（比如我们设为val，设什么都可以）步，长短链表再开始同步遍历，找相同的节点。

2、解题过程

像这种题目拿到手我们首先就是想到要画图，一定要有这个意识，数据结构的算法题一定要画图。

两个链表相交有哪几种情况？如下图所示—— 

如何判断链表是否相交？ 

两个链表的尾节点相同，两个链表一点相交

接下来我们就可以写代码了—— 

值得注意的是：

（1）链表开始往后走的时候，我们要计算A链表的长度，所以我们还得要两个计数器，定义计数器的目的也是计算每个链表里面节点的个数。

（2）int gap = abs(sizeA - sizeB);

//abs()——求绝对值——C语言库里面提供的库方法。

（3）这里shortList、longList在同一起跑线上了，while(shortList)或者用while(longList)都是一样的，这里判断如果是，两个链表就相交了。

 代码演示：

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ typedef struct ListNode ListNode;struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { //求链表的长度 ListNode* pa = headA; ListNode* pb = headB; //开始往后走的时候，我们要计算A链表的长度，所以我们还得要两个计数器 //定义计数器，计算每个链表里面节点的个数 int sizeA = 0,sizeB = 0; while(pa) { sizeA++; pa = pa->next; } while(pb) { sizeB++; pb = pb->next; } //求长度差 int gap = abs(sizeA - sizeB);//求绝对值——C语言库里面提供的库方法 //定义长短链表 ListNode* shortList = headA; ListNode* longList = headB; if(sizeA > sizeB) { longList = headA; shortList = headB; } //让长链表先走gap while(gap--)//比如1 { longList = longList->next; } //shortList longList在同一起跑线 //这里如果是，就相交了 while(shortList) //或者用while(longList) { if(shortList == longList) { return shortList; } shortList = shortList->next; longList = longList->next; } //链表不相交 return NULL;}

复杂度：时间复杂度：O(N)，空间复杂度：O(1)。

虽然有循环，但都是并列的关系，没有嵌套，时间复杂度O(N)。

结尾

往期回顾：

【牛客&LeetCode&数据结构】单链表的应用——移除链表元素问题、链表分割问题详解

【牛客&LeetCode&数据结构】单链表的应用——合并两个有序链表问题、链表的回文结构问题详解

【LeetCode&数据结构】单链表的应用——反转链表问题、链表的中间节点问题详解

【LeetCode】用双指针解决移除元素问题、合并两个有序数组求解

【LeetCode】力扣题——轮转数组、消失的数字、数组串联

结语：本篇文章到这里就结束了，本文讲述的两道代码题并不适合C语言初学者，需要有一定的C语言基础，最好要学过数据结构与算法的算法复杂度和链表的知识，才能写出复杂度较优的代码来。大家一定要自己动手敲一敲，不敲的话不仅容易忘记，也不方便将来复习。