【数据结构与算法】链表之美-复杂链表的复制与链表的插入排序

主页：HABUO🍁主页：HABUO

🍁如果再也不能见到你，祝你早安，午安，晚安🍁

1.复杂链表的复制

题目：请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

示例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]]

分析：这是一个比较复杂的题目，我们只有见的多了之后我们可能看到这样新的题目，才会有敲门砖，又时候差的就是刚开始的敲门砖，敲门砖有了，剩下的就是用我们之前拥有的思想去实现就完了。因此呢，在这里我直接给出这个思路，以后再遇到这样类型的我们是不是就会了啊。首先，我们直接遍历是不是没办法搞啊，因为你random不知道指向谁，有些人可能会说，那我直接访问该节点的random不就行了，是的，但是如果我们链表当中，有两个相同值的节点怎么办？因为我们复制节点是复制它们的值和指向，地址是不是同等的复制下来，假如两个3，你只知道random指向3的那个节点，但是具体哪个节点我们是不是无能为力啊。因此这种直接的方法难以实现。好了，接下来很重要，1.我们为每一个节点备份一个节点，而且呢，让这个节点的next指向这个备份节点，让备份节点的next指向原链表该节点的next。2.让每一个备份节点的random指向它应该指向的备份节点，有人会问，那这咋指向，好关键点来了，你发现没有，备份节点的random是不是就是原节点的random的next啊，对不对，这就是这个题的关键。3.恢复原链表，让新链表链接起来，并返回头指针。这就是我们整体的思路。下面进行一步一步实现。

第一步：为每个节点进行备份，并且让这个节点的next指向这个备份节点，让备份节点的next指向原链表该节点的next，由于random画上之后错综复杂，不再指出，本题以示例1为导向。如下图所示：

代码实现如下：

//1.为每个链表节点备份一个节点Node* cur = head;while(cur){Node* copyNode = (Node*)malloc(sizeof(Node));copyNode->val = cur->val;copyNode->next = cur->next;cur->next = copyNode;cur = copyNode->next;}

第二步让每一个备份节点的random指向它应该指向的备份节点，我们以13节点为例，看下图就会明白。因为每一个节点的备份节点是不是就是原节点的next因此我们想要备份节点指向它所指向的random，找到原节点的random是不是就行了啊。

代码实现如下：

//2.为备份节点的random进行链接cur = head;while(cur){//cur->random有可能指向NULLif(cur->random == NULL){cur->next->random = NULL;cur = cur->next->next;continue;}//每个备份节点的random，都是原节点的random的备份节点cur->next->random = cur->random->next;cur = cur->next->next;}

第三步，我们破坏了原链表的链接是不是需要恢复，而且新链表也还没有连接上，下面是不是就是恢复和链接，这里就只需要多设置几个指针来回的走就ok，前面的几道题的铺垫，相信这对于我们来说应该相对很简单。

//恢复原链表，把备份链表进行链接cur = head;Node* newHead = cur->next;Node* copyCur = newHead;Node* curNext = newHead->next;while(cur){cur->next = curNext;if(curNext == NULL){copyCur->next = NULL;break;}copyCur->next = curNext->next;copyCur = copyCur->next;cur = curNext;curNext = curNext->next->next;}return newHead;

要注意curNext是不是到最后就为NULL了，但是我们下面还有要访问它的next的代码，因此需要在这之前做一个判断语句做一个判断，防止错误。需要注意我们这种方法是不是对原链表进行修改了，这种操作是不太好的，等到好面我们学习的深入会用更优的方法去解决。

2.对链表进行插入排序

题目：给定单个链表的头 head ，使用 插入排序 对链表进行排序，并返回 排序后链表的头 。

插入排序 算法的步骤:

插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
重复直到所有输入数据插入完为止。

示例1：

输入: head = [4,2,1,3] 输出: [1,2,3,4]

示例2：

输入: head = [-1,5,3,4,0] 输出: [-1,0,3,4,5]

分析：我们可能直接的想法就是从第一个数据起，拿到一个数据就从头遍历放到合适的位置直至最后一个节点。但是这是链表啊，这样操作是不是代价也太高了，要是数组你发到一个合适的位置，只需要将后面的数据往后移动即可，链表不太行。所以，我们的思路是，将第一个节点当作一个新链表的起始节点，之后从后面链表当中每次取一个节点，往新链表当中进行逐一比较进行插入，当然有可能头插，也有可能尾插，也可能中间插入，所以分三种情况，这就是我们的大致思想，具体如下图所示：

所以分三种情况进行插入，头插实现如下：注意我们一开始让head指向了head->next，因为我们让第一个节点当作新链表的头了。

//头插if(cur->val >= head->val){head->next = cur;cur = head;newHead = cur;head =headNext;if(headNext == NULL)break;headNext = headNext->next;continue;}

中间插入实现代码如下：

while(cur){//中间插入if(cur->val < head->val){curPrev = cur;cur = cur->next;}else{head->next = cur;curPrev->next = head;head = headNext;if(headNext == NULL)break;headNext = headNext->next;break;}}

尾插的话是不是就是中间插入情况的cur指向了NULL还没找到合适的位置，因此实现代码如下：

//尾插if(cur == NULL){curPrev->next = head;head->next = NULL;head = headNext;if(headNext == NULL)break;headNext = headNext->next;}

所以将这些代码串起来放到一个循环当中是不是就实现了，因此完整代码如下：

 typedef struct ListNode Node;
struct ListNode* insertionSortList(struct ListNode* head) {if(head == NULL || head->next == NULL)return head;Node* newHead = head;head = head->next;newHead->next = NULL;Node* headNext = head->next;while(head) {Node* cur = newHead;Node* curPrev = NULL;//头插if(cur->val >= head->val){head->next = cur;cur = head;newHead = cur;head =headNext;if(headNext == NULL)break;headNext = headNext->next;continue;}while(cur){//中间插入if(cur->val < head->val){curPrev = cur;cur = cur->next;}else{head->next = cur;curPrev->next = head;head = headNext;if(headNext == NULL)break;headNext = headNext->next;break;}}//尾插if(cur == NULL){curPrev->next = head;head->next = NULL;head = headNext;if(headNext == NULL)break;headNext = headNext->next;}}return newHead;
}