LeetCode刷题——单链表进阶（详细图解）

温馨提示：
做数据结构题的时候一定要多画图，考虑到特殊情况。

1、复制带随机指针的链表

知道整体思路后敲出代码就不难了

①创建结点

这里要注意判断原链表为空的情况

②链接结点

③random




先看第一个拷贝结点，从图中直接看他应该指向NULL，所以①的random指向NULL，这种情况应该特殊处理
再看第二个拷贝结点，通过原结点看②应该指向①，那么用代码如何表示呢？
假设val为13的结点的指针为p

那么①的结点就可以表示为 p->random->next

④链接拷贝结点后返回

/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *next;
 *     struct Node *random;
 * };
 */

struct Node* copyRandomList(struct Node* head) {
   
    if(head == NULL)
    {
   
        return NULL;
    }
	struct Node* cur = head;
    //链接拷贝结点
    while(cur)
    {
   
        struct Node* next = cur->next;
        struct Node* tmp = (struct Node*)malloc(sizeof(struct Node));
        tmp->val = cur->val;
        cur->next = tmp;
        tmp->next = next;
        cur = next;
    }
    //random
    cur = head;
    while