数据结构与算法⑥(第二章OJ题，下)后八道链表面试题（中）:https://developer.aliyun.com/article/1513365
11. 返回链表的深度拷贝
138. 复制带随机指针的链表
难度中等
给你一个长度为 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：
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例 2：
输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]
示例 3：
输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]
提示：
- 0 <= n <= 1000
- -10^4 <= Node.val <= 10^4
- Node.random 为 null 或指向链表中的节点。
/** * Definition for a Node. * struct Node { * int val; * struct Node *next; * struct Node *random; * }; */ struct Node* copyRandomList(struct Node* head) { }
神奇代码：
很复杂的一题，要对链表增删查改很熟悉
可以用时间O(N^2)暴力法通过，会发现random非常的难处理
（因为原链表random的指向的节点在复制链表的对应的要指向的节点找不到了）
O(N^2)暴力法就是比较值是否相等，但是值有两个呢，这样又要麻烦了
以下是时间O(N)的很巧妙的方法：
struct Node* copyRandomList(struct Node* head) { //1.插入复制节点到原节点的后面 struct Node* cur = head; while (cur) { struct Node* copy = (struct Node*)malloc(sizeof(struct Node)); copy->val = cur->val; copy->next = cur->next;//插入copy节点 cur->next = copy; cur = copy->next; } //2.根据原节点处理复制节点的random cur = head; while (cur) { struct Node* copy = cur->next; if (cur->random == NULL) { copy->random = NULL; } else { copy->random = cur->random->next; } cur = copy->next; } //3.复制节点解下来链接成一个新链表，恢复原链表链接关系 struct Node* copy_head = NULL, * copy_tail = NULL; cur = head; while (cur) { struct Node* copy = cur->next; struct Node* next = copy->next; if (copy_head == NULL)//第一次进来 { copy_head = copy_tail = copy; } else { copy_tail->next = copy; copy_tail = copy; } cur->next = next; cur = next; } return copy_head; }
下面是后补的两道：
12. 对链表进行插入排序
（因为是穿越回来补的两道，所以对插入排序不懂的可以看看下面的链接：）
数据结构与算法⑰(第五章_八大排序)(完整代码+动图+详解+对比)_GR C的博客-CSDN博客
147. 对链表进行插入排序
难度中等
给定单个链表的头 head ，使用 插入排序 对链表进行排序，并返回 排序后链表的头 。
插入排序 算法的步骤:
- 插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
- 每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
- 重复直到所有输入数据插入完为止。
下面是插入排序算法的一个图形示例。部分排序的列表(黑色)最初只包含列表中的第一个元素。每次迭代时，从输入数据中删除一个元素(红色)，并就地插入已排序的列表中。
对链表进行插入排序。
示例 1：
输入: head = [4,2,1,3]
输出: [1,2,3,4]
示例 2：
输入: head = [-1,5,3,4,0]
输出: [-1,0,3,4,5]
提示：
- 列表中的节点数在 [1, 5000]范围内
- -5000 <= Node.val <= 5000
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* insertionSortList(struct ListNode* head){ }
代码：
struct ListNode* insertionSortList(struct ListNode* head) { struct ListNode* new_head = malloc(sizeof(struct ListNode)); new_head->val = 0; new_head->next = head;//新开一个节点指向头，最后返回这个节点的next struct ListNode* end = head;//设置end是已经插入好的链表的最后一个 struct ListNode* cur = head->next; while (cur) { if (end->val <= cur->val) //找比 已经插入好的最后一个 小的 { end = end->next; } else { struct ListNode* prev = new_head; while (prev->next->val <= cur->val) //找到了就再找cur应该插入的位置 { prev = prev->next; } //插入 end->next = cur->next; cur->next = prev->next; prev->next = cur; } cur = end->next;//cur=已经插入好的链表的最后一个的下一个，重复循环 } struct ListNode* ret = new_head->next; free(new_head); return ret; }
13. 删除链表中重复的结点
删除链表中重复的结点_牛客题霸_牛客网 (nowcoder.com)
JZ76 删除链表中重复的结点
中等 通过率：22.17% 时间限制：1秒 空间限制：64M
描述
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表 1->2->3->3->4->4->5 处理后为 1->2->5
数据范围：链表长度满足 0≤n≤1000 ，链表中的值满足 1≤val≤1000
进阶：空间复杂度 O(n) ，时间复杂度 O(n)
例如输入{1,2,3,3,4,4,5}时，对应的输出为{1,2,5}，对应的输入输出链表如下图所示：
示例1
输入：
{1,2,3,3,4,4,5}
复制
返回值：
{1,2,5}
复制
示例2
输入：
{1,1,1,8}
复制
返回值：
{8}
/** * struct ListNode { * int val; * struct ListNode *next; * }; */ /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param pHead ListNode类 * @return ListNode类 */ struct ListNode* deleteDuplication(struct ListNode* pHead ) { }
代码：
struct ListNode* deleteDuplication(struct ListNode* pHead ) { if(pHead == NULL) { return NULL; } struct ListNode* new_head = malloc(sizeof(struct ListNode)); new_head->val = 0; new_head->next = pHead;//新开一个节点指向头，最后返回这个节点的next struct ListNode* cur = new_head; while(cur->next && cur->next->next) { if(cur->next->val == cur->next->next->val) { int tmp = cur->next->val;//遇到两个节点相同的，记录下来并跳过 while(cur->next && tmp == cur->next->val) { cur->next = cur->next->next; } } else { cur = cur->next; } } return new_head->next; }
严谨代码：
ListNode* deleteDuplication(ListNode* pHead) { if (pHead == NULL || pHead->next == NULL) return pHead; struct ListNode* n0 = NULL; struct ListNode* n1 = pHead; struct ListNode* n2 = n1->next; while (n2 != NULL) { //如果相邻节点不相同，则不需要删除，更新节点，继续向后遍历 if (n1->val != n2->val) { n0 = n1; n1 = n2; n2 = n2->next; } else { //如果相邻节点相同 //则n2去找第一个不相同的节点 while (n2 && n2->val == n1->val) { n2 = n2->next; } //重新链接，如果要删除的包括头节点，则更新头节点 if (n0) n0->next = n2; else pHead = n2; // 删除掉重复的节点 while (n1 != n2) { struct ListNode* next = n1->next; free(n1); n1 = next; } //更新节点 n1 = n2; if (n2) n2 = n2->next; } } return pHead; }
链表其它题链接：
力扣:https://leetcode.cn/tag/linked-list/problemset/
牛客https://www.nowcoder.com/exam/oj
本篇完。
