链表面试题（C 语言）
1. 移除链表元素标题形貌： 给你一个链表的头节点 head 和一个整数 val ，请你删除链表中全部满意 Node.val == val 的节点，并返回 新的头节点 。
示例 1：
https://i-blog.csdnimg.cn/direct/04af34cfc0da4a39ba9d57aa6a73c241.png
输入：head = , val = 6
输出：
示例 2：
输入：head = [], val = 1
输出：[]
示例 3：
输入：head = , val = 7
输出：[]
提示：
列表中的节点数目在范围 内
1 <= Node.val <= 50
0 <= val <= 50
标题OJ链接： link
解题思绪： 起首判断链表是否为空，为空返回 NULL。其次利用循环举行头删判断，实行完全部的头删后，存储新头节点的位置。末了遍历链表，对包含指定元素节点举行删除。返回新头节点的位置。
代码如下：
typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) {
// 空表
if (NULL == head)
return NULL;
// 头删
ListNode* cur = head;
while (cur && cur->val == val)
{
// 存储下一个节点
ListNode* next = cur->next;
// 删除头节点
free(cur);
// 新头节点
cur = next;
}
// 空表或只剩一个节点
if (NULL == cur || NULL == cur->next)
{
return cur;
}
// 存储新头节点的位置
head = cur;
// 遍历链表，对剩下的包含指定元素的节点进行删除
ListNode* pre = head;
cur = head->next;
while (cur)
{
// 存储下一个节点
ListNode* next = cur->next;
// 删除
if (cur->val == val)
{
// 删除当前结点
free(cur);
// 前后重新链接
pre->next = next;
}
else
{
pre = pre->next;
}
// 下一个节点
cur = next;
}
// 返回新链表的头节点
return head;
}
2. 反转链表
标题形貌： 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
https://i-blog.csdnimg.cn/direct/54521a5a5360492f9a1430cde2af2b89.png
输入：head =
输出：
示例 2：
https://i-blog.csdnimg.cn/direct/51ec275c498749629fac2f043dd9faf1.png
输入：head =
输出：
示例 3：
输入：head = []
输出：[]
提示：
链表中节点的数目范围是
-5000 <= Node.val <= 5000
标题OJ链接： link
解题思绪：
方法一
利用三个指针 pre、cur 和 next 它们的初值分别为 NULL、head 和 head->next。然后让 cur->next = pre 产生逆序，接着三个指针都今后走一步，继续逆序，直到 cur == NULL 。此时 pre 就是逆置后链表的头节点，返回 pre 即可。
https://i-blog.csdnimg.cn/direct/2094c88574c8412caaace216d229c201.png
代码如下：
typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {
// 空表或者一个节点
if (NULL == head || NULL == head->next)
return head;
// 至少两个节点
ListNode* pre = NULL;
ListNode* cur = head;
while (cur)
{
// 存储下一个节点的位置
ListNode* next = cur->next;
// 逆置当前节点
cur->next = pre;
// 下一组
pre = cur;
cur = next;
}
// 返回逆置链表头节点
return pre;
}
方法二
利用一个函数 reverse_list() 举行递归来完成，该函数的函数原型如下：
void reverse_list(ListNode* pre, ListNode* cur);
是用该方法需要提前存储尾节点作为逆置链表的头节点返回。
代码如下：
typedef struct ListNode ListNode;
void reverse_list(ListNode* pre, ListNode* cur)
{
if (cur)
{
// 下一层递归
reverse_list(cur, cur->next);
// 逆序
cur->next = pre;
}
}
struct ListNode* reverseList(struct ListNode* head) {
// 空表或者一个节点
if (NULL == head || NULL == head->next)
return head;
// 存储尾节点
ListNode* tail = head;
while (tail->next)
tail = tail->next;
// 递归
ListNode* pre = NULL;
ListNode* cur = head;
reverse_list(pre, cur);
// 返回逆置链表头节点
return tail;
}
3. 链表的中间节点
标题形貌： 给你单链表的头结点 head ，请你找出并返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
示例 1：
https://i-blog.csdnimg.cn/direct/c99f2ddb770b4ed38df7871765ca9a56.png
输入：head =
输出：
解释：链表只有一个中间结点，值为 3 。
示例 2：
https://i-blog.csdnimg.cn/direct/a53fb155699040ab8e8e11f33415d600.png
输入：head =
输出：
解释：该链表有两个中间结点，值分别为 3 和 4 ，返回第二个结点。
提示：
链表的结点数范围是
1 <= Node.val <= 100
标题OJ链接： link
解题思绪： 利用快慢指针 fast 和 slow，两个指针都从链表头节点开始，快指针一次走两步，满指针一次走一步，当快指针走到末了一个节点或者为 NULL 时，满指针就在中间节点的位置。返回 slow。
代码如下：
typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {
ListNode* fast = head;
ListNode* slow = head;
while (fast && fast->next)
{
// 快指针两步，慢指针一步
fast = fast->next->next;
slow = slow->next;
}
// 返回慢指针
return slow;
}
上述代码不需要判断 head 是否为 NULL，循环的条件语句会举行判断。有时候思绪想不到很正常，作者第一次做这道题也是先计算链表总长，然后再找中间节点。
4. 返回倒数第 k 个节点
标题形貌： 实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。
留意： 本题相对原题稍作改动
示例：
输入： 1->2->3->4->5 和 k = 2
输出： 4
说明：
给定的 k 保证是有效的。
标题OJ链接： link
解题思绪： 本题和上题雷同，也是快慢指针 fast 和 slow。既然是倒数第 k 个节点，那我先让快指针 fast 走 k 步，然后两个指针一起走，当 fast 走到 NULL 时，slow 就是倒数第 k 个节点的位置。由于本题的 k 是有效的，所以可以不用判断。
代码如下：
typedef struct ListNode ListNode;
int kthToLast(struct ListNode* head, int k) {
ListNode* fast = head;
ListNode* slow = head;
// 快指针先走 k 步
while (k--)
fast = fast->next;
// 快指针到 NULL 时，慢指针到要求位置
while (fast)
{
fast = fast->next;
slow = slow->next;
}
// 返回
return slow->val;
}
5. 合并两个有序链表
标题形貌： 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的全部节点组成的。
示例 1：
https://i-blog.csdnimg.cn/direct/fd8142ac998c4df8b5627b03241f319c.png
输入：l1 = , l2 =
输出：
示例 2：
输入：l1 = [], l2 = []
输出：[]
示例 3：
输入：l1 = [], l2 =
输出：
提示：
两个链表的节点数目范围是
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 分列
标题OJ链接： link
解题思绪： 本题可以参照合并两个有序数组。额外创建一个空链表，然后取出两个链表的头节点举行比力，把小的谁人尾插到新的链表，直到有一个链表取完为止。末了把没取完的链表链接在新链表后面。返回新链表。
这里利用带哨兵位的头节点更加方便，淘汰了许多判断，作者会把这两种方法均给出。
代码如下：
（1）带哨兵位头节点
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
ListNode* head1 = list1;
ListNode* head2 = list2;
// 申请哨兵位头节点
ListNode* head = (ListNode*)malloc(sizeof(ListNode));
ListNode* tail = head;
while (head1 && head2)
{
if (head1->val < head2->val)
{
// list1 头节点尾插
tail->next = head1;
tail = head1;
// 下一个
head1 = head1->next;
}
else
{
// list2 头节点尾插
tail->next = head2;
tail = head2;
// 下一个
head2 = head2->next;
}
}
// 链上剩下的节点
if (head1)
tail->next = head1;
else
tail->next = head2;
// 存储新表头节点
ListNode* ret = head->next;
// 释放哨兵位头节点
free(head);
// 返回
return ret;
}
（2）不带哨兵位头节点
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
// 空表判断
if (NULL == list1)
return list2;
if (NULL == list2)
return list1;
ListNode* head1 = list1;
ListNode* head2 = list2;
ListNode* head = NULL;
ListNode* tail = NULL;
while (head1 && head2)
{
// 当前需要插入的节点
ListNode* cur = NULL;
if (head1->val < head2->val)
{
// list1 头节点尾插
cur = head1;
// 下一个
head1 = head1->next;
}
else
{
// list2 头节点尾插
cur = head2;
// 下一个
head2 = head2->next;
}
// 头插判断
if (NULL == head)
{
head = tail = cur;
}
else // 尾插
{
tail->next = cur;
tail = cur;
}
}
// 把剩下的节点链上
if (head1)
tail->next = head1;
else
tail->next = head2;
// 返回
return head;
}
不带哨兵位头节点需要在开头判断空表，不然在链接剩下的节点部分还要判断一次。而带哨兵位头节点就不需要如此贫苦，但是需要释放哨兵位头节点。
6. 分割链表
标题形貌： 给你一个链表的头节点 head 和一个特定值 x ，请你对链表举行分隔，使得全部 小于 x 的节点都出现在 大于或等于 x 的节点之前。你不需要 保存 每个分区中各节点的初始相对位置。
示例 1：
https://i-blog.csdnimg.cn/direct/2d459805cc8d47a7b073a917d428b2e0.png
输入：head = , x = 3
输出：
示例 2：
输入：head = , x = 2
输出：
提示：
链表中节点的数目在范围 内
-100 <= Node.val <= 100
-200 <= x <= 200
标题OJ链接： link
解题思绪： 创建两个新链表，一个存储小于 x 的节点，另一个存储大于 x 的节点。遍历原链表，把相应节点尾插到两个新链表。末了把两个新链表链接在一起，返转头节点。
本题利用带哨兵位的头节点更加方便，淘汰了许多判断。当然，本题也会给出不带哨兵位头节点的方法。
代码如下：
（1）带哨兵位头节点
typedef struct ListNode ListNode;
struct ListNode* partition(struct ListNode* head, int x) {
// 空表判断
if (NULL == head)
return head;
// 申请哨兵位头节点
ListNode* head_b = (ListNode*)malloc(sizeof(ListNode));
ListNode* head_s = (ListNode*)malloc(sizeof(ListNode));
ListNode* tail_b = head_b;
ListNode* tail_s = head_s;
// 遍历链表
while (head)
{
if (head->val < x)
{
// 尾插小表
tail_s->next = head;
tail_s = head;
}
else
{
// 尾插大表
tail_b->next = head;
tail_b = head;
}
// 下一个节点
head = head->next;
}
// 大表尾后置空
tail_b->next = NULL;
// 链接两表
tail_s->next = head_b->next;
// 存储新表头节点
ListNode* ret = head_s->next;
// 释放哨兵位头节点
free(head_b);
free(head_s);
// 返回
return ret;
}
本代码末了必须先是大表尾后置空，再链接两表，顺序不能改变。因为哨兵位头节点创建的时候并没有初始化，其 next 为任意值。
（2）不带哨兵位头节点
typedef struct ListNode ListNode;
struct ListNode* partition(struct ListNode* head, int x) {
// 空表
if (NULL == head)
return head;
// 创建大小两表
ListNode* head_b = NULL;
ListNode* head_s = NULL;
ListNode* tail_b = NULL;
ListNode* tail_s = NULL;
// 遍历原链表
while (head)
{
if (head->val < x)
{
// 尾插小表
// 头插
if (NULL == head_s)
{
head_s = tail_s = head;
}
else// 尾插
{
tail_s->next = head;
tail_s = head;
}
}
else
{
// 尾插大表
// 头插
if (NULL == head_b)
{
head_b = tail_b = head;
}
else// 尾插
{
tail_b->next = head;
tail_b = head;
}
}
// 下一个结点
head = head->next;
}
// 全部大于 x
if (NULL == head_s)
return head_b;
// 全部小于 x
if (NULL == head_b)
return head_s;
// 两者均有
// 大表尾后置空
tail_b->next = NULL;
// 两表链接
tail_s->next = head_b;
// 返回
return head_s;
}
与带哨兵位头节点差别，这里的后半部分需要分三种情况：全部大于 x，全部小于 x，两个都有。
7. 回文链表
标题形貌： 给定一个链表的 头节点 head ，请判断其是否为回文链表。如果一个链表是回文，那么链表节点序列从前今后看和从后往前看是雷同的。
示例 1：
https://i-blog.csdnimg.cn/direct/c375acc8a7db48afba87e3ad36d74d7c.png
输入: head =
输出: true
示例 2：
https://i-blog.csdnimg.cn/direct/be371ca48257451580b8c3eff13967a3.png
输入: head =
输出: false
提示：
链表 L 的长度范围为
0 <= node.val <= 9
标题OJ链接： link
标题思绪： 起首找到链表的中间节点，然后逆置链表的后半部分。接着比力前后部分是否雷同，不雷同则返回 false，雷同返回 true。
https://i-blog.csdnimg.cn/direct/d133318dba09483fbc44eb55a9268026.png
代码如下：
typedef struct ListNode ListNode;
bool isPalindrome(struct ListNode* head){
// 一个节点
if (NULL == head->next)
return true;
// 寻找中间节点
ListNode* fast = head;
ListNode* slow = head;
while (fast && fast->next)
{
fast = fast->next->next;
slow = slow->next;
}
ListNode* mid = slow;
// 逆置后半段
ListNode* pre = NULL;
ListNode* cur = mid;
while (cur)
{
// 存储下一个节点
ListNode* next = cur->next;
// 逆置
cur->next = pre;
// 下一组
pre = cur;
cur = next;
}
// 比较
ListNode* head_front = head;
ListNode* head_back = pre;
while (head_back)
{
// 不是回文
if (head_front->val != head_back->val)
return false;
// 下一组
head_front = head_front->next;
head_back = head_back->next;
}
// 是回文
return true;
}
8. 相交链表
标题形貌： 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：
https://i-blog.csdnimg.cn/direct/e9b1dd6835c1479d938a7ef802d258a6.png
标题数据 保证 整个链式结构中不存在环。
留意，函数返回结果后，链表必须 保持其原始结构 。
示例 1：
https://i-blog.csdnimg.cn/direct/028ca663c2b6492289939d1f00f33f68.png
输入：intersectVal = 8, listA = , listB = , skipA = 2, skipB = 3
输出：Intersected at ‘8’
解释：相交节点的值为 8 （留意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 ，链表 B 为 。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
— 请留意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是差别的节点。换句话说，它们在内存中指向两个差别的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向雷同的位置。
示例 2：
https://i-blog.csdnimg.cn/direct/0492bab0824f4192809355a678219f21.png
输入：intersectVal = 2, listA = , listB = , skipA = 3, skipB = 1
输出：Intersected at ‘2’
解释：相交节点的值为 2 （留意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 ，链表 B 为 。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
示例 3：
https://i-blog.csdnimg.cn/direct/8f41f22dac064045a13e82a3ed123ffa.png
输入：intersectVal = 0, listA = , listB = , skipA = 3, skipB = 2
输出：No intersection
解释：从各自的表头开始算起，链表 A 为 ，链表 B 为 。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。
提示：
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 == listB
标题OJ链接：link
解题思绪： 如果两个链表相交，那么它们的尾节点肯定雷同。遍历两个链表，找到尾节点的同时，计算其长度。如果尾节点雷同，那么让快指针指向长链表开头而且走两个链表的长度差值的绝对值步，然后让慢指针指向短链表开头，两个指针一起走，当它们指向同一个节点时，该节点就是相交节点。
https://i-blog.csdnimg.cn/direct/084ae9d5b29b4fb59523309a51b31582.png
代码如下：
typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
// 空表判断
if (NULL == headA || NULL == headB)
return NULL;
// 找到两个链表的尾节点，并计算两个链表的长度
ListNode* curA = headA;
ListNode* curB = headB;
int lenA = 1;
int lenB = 1;
while (curA->next)
{
++lenA;
curA = curA->next;
}
while (curB->next)
{
++lenB;
curB = curB->next;
}
// 尾节点不相同
if (curA != curB)
return NULL;
// 长链表先走 abs(lenA - lenB) 步
int k = abs(lenA - lenB);
ListNode* long_list = headA;
ListNode* short_list = headB;
if (lenA < lenB)
{
long_list = headB;
short_list = headA;
}
while (k--)
long_list = long_list->next;
// 两表一起走，直到相遇
while (long_list != short_list)
{
long_list = long_list->next;
short_list = short_list->next;
}
//返回
return long_list;
}
9. 环形链表
标题形貌： 给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过一连跟踪 next 指针再次到达，则链表中存在环。 为了表现给定链表中的环，评测体系内部利用整数 pos 来表现链表尾连接到链表中的位置（索引从 0 开始）。留意：pos 不作为参数举行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
示例 1：
https://i-blog.csdnimg.cn/direct/4bad680a2de348f19e081429cbd015cc.png
输入：head = , pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
https://i-blog.csdnimg.cn/direct/e7e9dd7c37724843928fb23ac2d908ea.png
输入：head = , pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
https://i-blog.csdnimg.cn/direct/59a3721b82d34bd18981936be50f534b.png
输入：head = , pos = -1
输出：false
解释：链表中没有环。
提示：
链表中节点的数目范围是
-105 <= Node.val <= 105
pos 为 -1 或者链表中的一个 有效索引 。
标题OJ链接： link
解题思绪： 利用快慢指针，快指针每次走一步，慢指针每次走两步，如果快指针能追上慢指针就证实该链表中有环。如果该链表有环，假设该环的长度为 n，那么两个指针肯定会进入环内，假设当慢指针刚进入环时，它与快指针的距离为 x，那么 x 的范围为 ，只要 n 是一个有限值，那么快指针肯定能追上慢指针。
因为快慢指针每次走的距离差值为 1，如果不是 1，那么就不肯定能追上。
代码如下：
typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head) {
ListNode* fast = head;
ListNode* slow = head;
while (fast && fast->next)
{
fast = fast->next->next;
slow = slow->next;
// 追上
if (fast == slow)
return true;
}
// 没环
return false;
}
10. 返回入环的第一个节点
标题形貌： 给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过一连跟踪 next 指针再次到达，则链表中存在环。 为了表现给定链表中的环，评测体系内部利用整数 pos 来表现链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。留意：pos 不作为参数举行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
示例 1：
https://i-blog.csdnimg.cn/direct/4428c1c2f95a4aa293a23250a96816ea.png
输入：head = , pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
https://i-blog.csdnimg.cn/direct/45b9fadf0fae433b98889763281a647c.png
输入：head = , pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
https://i-blog.csdnimg.cn/direct/ca43541f65c34a42b2456fe5f6f3a4f2.png
输入：head = , pos = -1
输出：返回 null
解释：链表中没有环。
提示：
链表中节点的数目范围在范围 内
-105 <= Node.val <= 105
pos 的值为 -1 或者链表中的一个有效索引
标题OJ链接： link
解题思绪： 先利用上一题的快慢指针法判断链表是否有环，如果有环就让慢指针回到链表开头，此时快指针在相遇点，两个指针一起走，相遇时所指向的节点就是入环的第一个节点。
https://i-blog.csdnimg.cn/direct/b81c59e0240e4f5f84eac82cbeef9799.png
代码如下：
typedef struct ListNode ListNode;
struct ListNode *detectCycle(struct ListNode *head) {
// 判断是否有环
ListNode* fast = head;
ListNode* slow = head;
int flag = 0;
while (fast && fast->next)
{
fast = fast->next->next;
slow = slow->next;
// 有环
if (fast == slow)
{
flag = 1;
break;
}
}
// 判断
if (0 == flag)
return NULL;
// slow 回归起始点，与 fast 一起走，相遇即使入环起点
slow = head;
while (slow != fast)
{
slow = slow->next;
fast = fast->next;
}
// 返回
return fast;
}
11. 随机链表的复制
标题形貌： 给你一个长度为 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 作为传入参数。
示例 1：
https://i-blog.csdnimg.cn/direct/d8563b676d0a419cb34e1e26973173ad.png
输入：head = [,,,,]
输出：[,,,,]
示例 2：
https://i-blog.csdnimg.cn/direct/4b5935e010e8405d913fba5275c919de.png
输入：head = [,]
输出：[,]
示例 3：
https://i-blog.csdnimg.cn/direct/c3b1d4c1b4c34d3398a6a28da4ac5fbc.png
输入：head = [,,]
输出：[,,]
提示：
0 <= n <= 1000
-104 <= Node.val <= 104
Node.random 为 null 或指向链表中的节点。
标题OJ链接： link
标题思绪： 把链表的每个节点拷贝一份，并链接在原节点的后面，这样你就会发现拷贝节点的 random 就在 random 的下一个，也就是 random->next。找到全部拷贝节点的 random 之后，然后把原链表的拷贝链表拆开，返回拷贝链表的头节点。
https://i-blog.csdnimg.cn/direct/23232bef3cc74a86b0ce4fd6b3da94af.png
代码如下：
typedef struct Node Node;
struct Node* copyRandomList(struct Node* head) {
// 空表
if (NULL == head)
return NULL;
// 拷贝每个节点并在其后插入
Node* cur = head;
while (cur)
{
// 申请新的节点
Node* new_node = (Node*)malloc(sizeof(Node));
if (NULL == new_node)
{
perror("copyRandomList::malloc: ");
exit(-1);
}
// 拷贝
new_node->val = cur->val;
new_node->random = cur->random;
// 链接
new_node->next = cur->next;
cur->next = new_node;
// 下一个结点
cur = cur->next->next;
}
// 找到每个拷贝节点的 random
cur = head;
while (cur)
{
// 拷贝节点
Node* cpy = cur->next;
// 找到 random
if (cpy->random)
cpy->random = cpy->random->next;
else
cpy->random = NULL;
// 下一个结点
cur = cur->next->next;
}
// 把原节点和拷贝节点拆开
cur = head;
Node* ret = cur->next;
while (cur)
{
// 拷贝节点
Node* cpy = cur->next;
// 断开链接
cur->next = cur->next->next;
if (cpy->next)
cpy->next = cpy->next->next;
else
cpy->next = NULL;
// 下一个
cur = cur->next;
}
// 返回拷贝链表的头节点
return ret;
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]