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

主页：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有可能指向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;
}