Leetcode 138.复制带随机指针的链表

?题目：

?示例：

?思路：

本题单纯复制链表的话很简单，难点在于还要复制另一个随机指针，这个随机指针无法通过多次遍历寻找(会有重复值)，所以目前有两种方法解答:

1. 节点地址的相对距离去寻找
2. 节点的绝对距离去寻找(从第一个节点开始找random的位置),时间复杂度为O(N²)

我们这里讲更为简单的第一种方法:

1.我们直接在每一个原节点的next插入我们所copy的节点，如(属于是不会用画图软件了?)

实现代码：

struct Node* cur = head; //原节点    while(cur)    { struct Node* copy = (struct Node*)malloc(sizeof(struct Node)); //扩容 copy->val = cur->val; //copy值 copy->next = cur->next; //复制原节点cur的next cur->next = copy; //让cur的next指向copy cur = cur->next->next; //此时第一个节点的next已经是我们copy的节点了，要想遍历到第二个原节点需要next两次    }

2.实现完第一步copy，接下来就是我们认为最棘手的random随机指针了，不过当我们将复制的节点插在原节点的next后，此时我们需要copy的random，不就是cur->random->next吗？

实现代码:

cur = head;    while(cur)    { struct Node* copy = cur->next; //从copy的头开始 if(cur->random == NULL) //特殊情况，random指向NULL时 {     copy->random = NULL; } else {     copy->random = cur->random->next; } cur = cur->next->next;    }

3.最后我们将copy的链表抽离(也就是尾插)出来即可：

实现代码：

cur = head;    struct Node* copyHead = NULL,* copyTail = NULL;    while(cur)    { struct Node* copy = cur->next; struct Node* Next = copy->next; cur->next = Next; if(copyTail == NULL) //第一个节点抽离 {     copyHead = copyTail = copy; } else {     copyTail->next = copy;     copyTail = copyTail->next; } cur = Next;    }

✔代码：

初始代码：

/** * Definition for a Node. * struct Node { *     int val; *     struct Node *next; *     struct Node *random; * }; */struct Node* copyRandomList(struct Node* head) {}

完整代码：

/** * Definition for a Node. * struct Node { *     int val; *     struct Node *next; *     struct Node *random; * }; */struct Node* copyRandomList(struct Node* head) {    struct Node* cur = head;    while(cur)    { struct Node* copy = (struct Node*)malloc(sizeof(struct Node)); copy->val = cur->val; copy->next = cur->next; cur->next = copy; cur = cur->next->next;    }    cur = head;    while(cur)    { struct Node* copy = cur->next; if(cur->random == NULL) {     copy->random = NULL; } else {     copy->random = cur->random->next; } cur = cur->next->next;    }    cur = head;    struct Node* copyHead = NULL,* copyTail = NULL;    while(cur)    { struct Node* copy = cur->next; struct Node* Next = copy->next; cur->next = Next; if(copyTail == NULL) {     copyHead = copyTail = copy; } else {     copyTail->next = copy;     copyTail = copyTail->next; } cur = Next;    }    return copyHead;}

✔大功告成！