C语言【数据结构】链表【OJ题（C++）练习】_c语言链表训练

目录

1.203. 移除链表元素

2.206. 反转链表

3.876. 链表的中间结点

4.链表中倒数第k个结点_牛客题霸_牛客网

5.21. 合并两个有序链表

6.链表分割_牛客题霸_牛客网

7.链表的回文结构_牛客题霸_牛客网

8.160. 相交链表

9.141. 环形链表

10.142. 环形链表 II

11.138. 复制带随机指针的链表

---

前言：单链表->C语言【数据结构】单链表实现_糖果雨滴a的博客-CSDN博客_c语言单链表的实现

带头双向循环链表->C语言【数据结构】链表（带头双向循环）实现_糖果雨滴a的博客-CSDN博客

1.203. 移除链表元素

（1）描述

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

示例 1：

输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

示例 2：

输入：head = [], val = 1
输出：[]

示例 3：

输入：head = [7,7,7,7], val = 7
输出：[]

（2）思路

方法1：类似于单链表中的删除接口。

        创建一个用来循环的节点cur，以及一个保存cur前一个结点的prev，通过while循环，循环到nullptr时停止，如果cur节点值不是val，先让prev = cur，然后再让链表往后走，这样prev就始终是cur的前一个值。

        如果cur节点的值为val，这时候要注意一种特殊情况，当头节点的值为val，那么要先保存头节点的下一个节点，然后delete掉头节点，再让下一个节点变成头节点。正常情况就通过让prev->next = cur -> next，直接连接起来，从而实现删除操作，之后再delete掉cur，同时让cur变成原本cur的下一个节点（现在是prev的下一个节点）

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* cur = head;
        ListNode* prev = nullptr;
        while(cur != nullptr)
        {
            // 不是val，链表往后走
            if(cur->val != val)
            {
                prev = cur;
                cur = cur->next;
            }
            // 是val
            else
            {
                // 头是val，delete掉当前头节点，让下一个节点作为新的头
                if(head->val == val)
                {
                    ListNode* next = head->next;
                    delete head;
                    head = next;
                    cur = next;
                }
                // 正常情况，让前一个节点连接上后一个节点，删掉值为val的节点
                else if(cur->val == val)
                {
                    prev->next = cur->next;
                    delete cur;
                    cur = prev->next;
                }
            }
        }
 
        return head;
    }
};

方法2：递归方法，链表一般都可以用递归的方式来做。

        我们可以把链表看做一个头节点head后面连接一个更短的链表，然后进行拆解，不断拆解，直到不能再拆解。head == nullptr的时候就说明不能再拆了。

        然后如果递归中head中的值等于val，那么就直接返回当前链表连接的情况（这样就可以让当前这个节点不参与到链表中，相当于删除了这个节点）。如果不等于，就让head->next = res，即让当前节点连接到链表之中，之后返回到res中。

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        if (head == nullptr) 
            return nullptr;  
 
        ListNode* res = removeElements(head->next, val);
 
        if (head->val == val) 
        {
            return res;
        } 
        else 
        {
            head->next = res;
            return head;
        }
    }
};

方法2写法优化：

        这个在写法上进行了优化，直接把结果存放到head->next中，这时候在判断head的值是否等于val时，我们要注意，如果是val，要返回head->next，这样才能跳过当前节点；然后不是val的时候，返回当前节点，才能连接上。

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        if(head == nullptr)
            return nullptr;
 
        head->next = removeElements(head->next, val);
        return head->val == val ? head->next : head;
    }
};

2.206. 反转链表

（1）描述

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

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

示例 2：

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

（2）思路

方法1：头插法，我们把后面的节点依次头插在第一个节点前面

我们创建一个newHead变量，这个就是最后新的头节点，以及一个cur变量。while循环，先保存当前节点的下一个节点，然后让当前节点连上新的头节点newHead，连上之后，这个节点就变成了新的头节点，cur = next，cur往下走，继续循环，直到结束。最后返回newHead即可

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* newHead = nullptr;
        ListNode* cur = head;
 
        while(cur != nullptr)
        {
            ListNode* next = cur->next;
            cur->next = newHead;
            newHead = cur;
            cur = next;
        }
 
        return newHead;
    }
};

方法2：调转方向法。创建3个指针，n1，n2，n3，然后通过这3个指针，依次改变链表中的方向。

        n2为从头到尾的指针，每次改变n2的下一个节点，让n2的下一个节点指向它的前一个结点n1，然后3个指针分别往后走，如果n3不是空指针，就让n3再往下走，因为最后n3一定会是空指针，所以要加上这一层判断，否则会报错。

        最后我们还要注意，因为n3在初始化时是头节点的下一个，所以当链表为空链表时，要提前结束，否则n3会因为非法访问报错。

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        // 下面n3是n2的下一个，如果head是空，就要提前判断，否则下面n3会非法访问
        if(head == nullptr)
        {
            return head;
        }
 
        ListNode* n1 = nullptr;
        ListNode* n2 = head;
        ListNode* n3 = n2->next;
 
        while(n2)
        {
            n2->next = n1;
            n1 = n2;
            n2 = n3;
            if(n3)
            {
                n3 = n3->next;
            }
        }
 
    return n1;
 
    }
};

方法3：递归法

        通过递归调用到链表的最后面，然后从后往前，改变链表方向

        首先两个判断，如果head为空，即链表为空时，直接返回头节点，如果head->next为空，说明走到链表尾，这时候返回头节点。

        我们创建一个新头，通过递归，递归到了最后一个节点时，返回，这时head，比如链表是1->2->3->4->5，这是我们的位置是处于4，newHead这时候是5（因为刚才递归到最后一个节点后就返回了）。这时候让head->next->next = head，即5的next指向4（head），这样就实现了5->4,但是这时候指向是1->2->3->4<->5，所以我们要让head->next = nullptr，这样就是1->2->3->4<-5了，这样依次从后往前进行，就可以完成反转。

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == nullptr || head->next == nullptr)
        {
            return head;
        }
 
        ListNode* newHead = reverseList(head->next);
 
        head->next->next = head;
        head->next = nullptr;
 
        return newHead;
    }
};

3.876. 链表的中间结点

（1）描述

给定一个头结点为 head 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

示例 1：

输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])

返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.

示例 2：

输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])

由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。

（2）思路

方法1：数组法

        这个比较容易想，因为链表无法通过下标去找到对应的元素，那么我们可以创建一个数组，放入数组中，然后 数组元素个数 / 2 就是中间节点了。

方法2：单指针法

        这个是对方法1的优化，节省了空间。只需要遍历两遍链表，第一遍记录链表元素个数，第二遍遍历到 个数 / 2 返回即可。

方法3：快慢指针法

        这个是最好的方法，只需要遍历一遍链表。通过定义两个指针变量，一个快指针，一个慢指针，然后同时往后遍历，快指针一下走两步，慢指针一下走一步，这样等快指针走到链表尾的时候，慢指针正好走到中间节点。

方法3代码：

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* fast = head, *slow = head;
        while(fast != nullptr && fast->next != nullptr)
        {
            fast = fast->next->next;
            slow = slow->next;
        }
 
        return slow;
    }
};

4.链表中倒数第k个结点_牛客题霸_牛客网

（1）描述

输入一个链表，输出该链表中倒数第k个结点。

示例1

输入：

1,{1,2,3,4,5}

复制返回值：

{5}

（2）思路

方法1：要求得倒数第k个节点，那么我们可以转换成正数的。

        两次遍历，第一次遍历求出链表元素个数，然后把倒数转换成正数的，第二遍再遍历到正数的链表元素，并返回。

方法2：快慢指针法

        定义两个指针变量，一个快指针，一个慢指针，想要得到倒数第k个元素，那么可以先让快指针fast先走k步，然后再让两个指针一起走，这时候因为fast先走了k步，所以fast会比slow快k步，这时候slow正好是倒数第k个元素。

方法2代码：

class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
        ListNode* fast = pListHead, *slow = pListHead;
        while(k--)
        {
            // k > 链表中的元素个数时
            if(fast == nullptr)
            {
                return nullptr;
            }
            // 正常往下走
            fast = fast->next;
        }
        
        while(fast)
        {
            fast = fast->next;
            slow = slow->next;
        }
        
        return slow;
    }
};

5.21. 合并两个有序链表

（1）描述

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：

输入：l1 = [], l2 = []
输出：[]

示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

（2）思路

方法1：迭代法

        创建两个变量，作为新的链表的头和尾。用归并的思想，list1的小，就链接上list1的节点，list2的小，就链接上list2的节点，这里要注意，第一个进来的节点，要变成这个新链表的头。链接交给尾指针，每次链接新节点，都更改尾指针。最后判断list1和list2是否有剩余的节点，若有，则链接上。

        这里要注意list1和list2存在空链表的情况，list1为空，就返回list2；list2为空，就返回list1。

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        // list1为空链表
        if(list1 == nullptr)
            return list2;
 
        // list2为空链表
        if(list2 == nullptr)
            return list1;
 
        ListNode* head = nullptr, *tail = nullptr;
 
        while(list1 && list2)
        {
            // list1小于list2
            if(list1->val < list2->val)
            {
                // 第一个进入循环的节点，作为头节点
                if(tail == nullptr)
                {
                    head = list1;
                    tail = list1;
                }
                // 尾插，尾连接下一个节点，并让下一个节点变成新的尾
                else
                {
                    tail->next = list1;
                    tail = list1;
                }
 
                list1 = list1->next;
            }
            else
            {
                // 第一个进入循环的节点，作为头节点
                if(tail == nullptr)
                {
                    head = list2;
                    tail = list2;
                }
                else
                {
                    tail->next = list2;
                    tail = list2;
                }
 
                list2 = list2->next;
            }
        }
 
        // list1有剩余的节点
        if(list1)
        {
            tail->next = list1;
        }
 
        // list2有剩余的节点
        if(list2)
        {
            tail->next = list2;
        }
 
        return head;
    }
};

方法2：递归法

        使用递归分解了很多子问题，每个子问题都是一个在当前的链表中找到最小的一个节点，被连接在前一个最小的节点后面。连接之后，返回去才是真正链接上了。

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        // list1为空链表
        if(list1 == nullptr)
            return list2;
 
        // list2为空链表
        if(list2 == nullptr)
            return list1;
 
        if(list1->val < list2->val)
        {
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        }
        else
        {
            list2->next = mergeTwoLists(list1, list2->next);
            return list2;
        }
    }
};

6.链表分割_牛客题霸_牛客网

（1）描述

现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。

（2）思路

         创建两个新的链表，并且都带一个哨兵位的头节点，两个链表分别定义一个头和一个尾，哨兵位的头用来后面链接与返回，尾用来链接每一个节点。

        小于x的节点插在lessTail的后面，大于x的节点插在greaterTail的后面。最后再把greaterTail的下一个节点置空，让lessTail链接上greaterTail。

class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        // write code here
        ListNode* lessHead, *lessTail, *greaterHead, *greaterTail;
        lessHead = lessTail = new ListNode(0);
        greaterHead = greaterTail = new ListNode(0);
        
        lessTail->next = nullptr;
        greaterTail->next = nullptr;
        
        ListNode* cur = pHead;
        while(cur)
        {
            // 小于x的节点插在lessTail的后面
            if(cur->val < x)
            {
                lessTail->next = cur;
                lessTail = cur;
            }
            // 大于x的节点插在greaterTail的后面
            else
            {
                greaterTail->next = cur;
                greaterTail = cur;
            }
            
            // cur往后走
            cur = cur->next;
        }
        
        // 大的那个链表后面为空
        greaterTail->next = nullptr;
        // 小的那个链表后面链接大的链表
        lessTail->next = greaterHead->next;
        
        // 下面要销毁，提前保存一下
        ListNode* list = lessHead->next;
        
        delete lessHead;
        delete greaterHead;
        
        return list;
    }
};

7.链表的回文结构_牛客题霸_牛客网

（1）描述

对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。

给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。

示例：

1->2->2->1

返回：true

（2）思路

        想要判断是否是回文结构，那么我们可以先得到中间的节点，再把中间节点后面的所有节点都进行反转处理，这时如果是回文结构，那么对应的节点的值应该都相等。因此可以通过这个进行比较，全相等说明是回文结构。

        首先是求得中间节点，这里我们可以通过快慢指针来完成，但是要注意节点个数为奇数还是偶数时，同时也要注意是否为空链表。因此这里判断条件是fast && fast->next，最后返回慢指针。

        然后是让中间节点后面的节点反转，这个与上面的第2题相同->2. 206. 反转链表

         最后两段依次进行比较，有一个不相同就说明不是回文结构。

class PalindromeList {
public:
    ListNode* middleNode(ListNode* head)
    {
        ListNode* fast = head, *slow = head;
        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        
        return slow;
    }
    
    ListNode* reverseList(ListNode* head)
    {
        ListNode* newHead = nullptr;
        ListNode* cur = head;
        while(cur)
        {
            ListNode* next = cur->next;
            cur->next = newHead;
            newHead = cur;
            cur = next;
        }
        
        return newHead;
    }
    
    bool chkPalindrome(ListNode* A) {
        // write code here
        
        // 得到中间节点
        ListNode* mid = middleNode(A);
        // 得到从中间到最后一个节点的倒序链表
        ListNode* rHead = reverseList(mid);
        
        // 前半段与后半段的倒序版比较，全部相等说明是回文结构
        while(A && rHead)
        {
            if(A->val == rHead->val)
            {
                A = A->next;
                rHead = rHead->next;
            }
            else
            {
                return false;
            }
        }
        
        return true;
    }
};

8.160. 相交链表

（1）描述

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

自定义评测：

评测系统 的输入如下（你设计的程序 不适用 此输入）：

intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
listA - 第一个链表
listB - 第二个链表
skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数
评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'

解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

示例 2：

输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'

解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null

解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。

（2）思路

        双指针法

        首先求出两个链表的长度，然后随便令一个链表为长链表，另一个链表就为短链表，这时候再用之前求出的长度判断一下是否符合。然后再让长的那个链表走差距步（两个长度的差值），这时候走完差距步时，两个链表处于相对应的位置上。

        之后再让两个链表一起往后走，这时候因为是在相对应的位置上，所以如果后面有一个相同的节点，就可以说明两个链表相交，如果链表走完，没有一个相同的节点，就说明两个链表不相交。

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* tailA = headA, *tailB = headB;
        int lenA = 0, lenB = 0;
 
        // 求出链表A的节点个数
        while(tailA)
        {
            ++lenA;
            tailA = tailA->next;
        }
 
        // 求出节点B的节点个数
        while(tailB)
        {
            ++lenB;
            tailB = tailB->next;
        }
 
        // 默认A是长链表，B是短链表
        ListNode* longList = headA, *shortList = headB;
        // 如果B节点多，那么更改B为长链表，A为短链表
        if(lenB > lenA)
        {
            longList = headB;
            shortList = headA;
        }
 
        // 算出长度差
        int gap = abs(lenA - lenB);
 
        // 长链表走差距步
        while(gap--)
        {
            longList = longList->next;
        }
 
        // 长和短链表同时走，这时位置相对应
        // 如果后面有相同的节点，说明链表相交
        // 如果走到最后，也没有相同的节点，说明链表不相交
        while(longList && shortList)
        {
            if(longList == shortList)
            {
                return longList;
            }
 
            longList = longList->next;
            shortList = shortList->next;
        }
 
        return nullptr;
    }
};

9.141. 环形链表

（1）描述

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true

解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：true

解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：false

解释：链表中没有环。

（2）思路

        快慢指针法

        快指针一次走两步，慢指针一次走一步，那么如果有环，快指针会先进入环，这时候等到慢指针进入环，快指针可能已经转了好几圈了，但是无论如何，因为快指针和慢指针只差一步，所以一定会在环内相遇。

        如果没有相遇，就说明没有环。

注意：这个快慢指针中间必须只能差一步，比如：快指针一次走3步，慢指针一次走1步，那么如果距离入口点是奇数就永远也追不上了

class Solution {
public:
    bool hasCycle(ListNode *head) { 
        ListNode* fast = head, *slow = head;
        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
 
            if(fast == slow)
            {
                return true;
            }
        }
 
        return false;
    }
};

10.142. 环形链表 II

（1）描述

给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点

解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点

解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：返回 null

解释：链表中没有环。

（2）思路

        先判断是否有环，如果有环，我们就可以用结论：两个指针，一个指针从快慢指针相遇的地方走，一个指针从链表头走，最终它们会在入口点（环口）相遇。

链表头~入口点距离：L

链表头~相遇点距离：X

环的长度：C

fast一次走两步，slow一次走一步，那么fast走的距离是slow的两倍

slow走的距离：L+X

fast走的距离：L + N * C + X

2 * (L + X) = L + N * C  +X

L + X = N * C

L = N * C - X

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        // 先判断是否有环（快慢指针法）
        ListNode* fast = head, *slow = head;
        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
 
            // 快慢指针相遇
            if(slow == fast)
            {
                // meet是快慢指针相遇的位置
                // 结论：一个指针从meet走，一个指针从head走，最终它们会在入口点（环口）相遇
                // L = N*C-X <=> L = (N-1)*C+(C-X)
                ListNode* meet = fast;
                while (head != meet)
                {
                    head = head->next;
                    meet = meet->next;
                }
 
                return meet;
            }
        }
 
        return nullptr;
    }
};

11.138. 复制带随机指针的链表

（1）描述

给你一个长度为 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]]

（2）思路

        这道题我们可以用三步去复制这个带随机指针的链表。

        第一步：先拷贝节点在原节点的后面

        第二步：再链接上拷贝节点的random指针

        第三步：最后解下拷贝的节点，并把拷贝的节点链接起来

class Solution {
public:
    Node* copyRandomList(Node* head) {
        // 1.拷贝节点在原节点后面
        Node* cur = head;
        while(cur)
        {
            Node* copy = new Node(cur->val);
            copy->next = cur->next;
            cur->next = copy;
            cur = cur->next->next;
        }
 
        // 2.链接拷贝节点的random
        cur = head;
        while(cur)
        {
            Node* copy = cur->next;
 
            if(cur->random == nullptr)
            {
                copy->random == nullptr;
            }
            else
            {
                // 链接的是拷贝的节点，所以copy->random要等于cur->random->next
                copy->random = cur->random->next;
            }
            cur = cur->next->next;
        }
 
        // 3.解下拷贝的节点，并把拷贝的节点链接起来
        cur = head;
        Node* copyHead = nullptr, *copyTail = nullptr;
        while(cur)
        {
            Node* copy = cur->next;
            Node* next = copy->next;
            cur->next = next;
 
            if(copyHead == nullptr)
            {
                copyHead = copy;
                copyTail = copy;
            }
            else
            {
                copyTail->next = copy;
                copyTail = copy;
            }
 
            cur = next;
        }
 
        return copyHead;
    }
};