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有可能指向NULL
if(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;
}总结：本篇博客介绍了两个有关链表的两个题，相对于前面我们所介绍的题，可能有些难度，但这些难度是不是都是在思路上，如果有了这个思路实现起来是不是还是用我们前面的思想啊，因此我们别畏惧它，相信通过夜以继日的敲代码，我们肯定会拿到一个难题就会有思路的。大家加油！💯