后插节点解答

        实现目标，要将复杂问题拆解为较为解决的较小问题进行逐步解决。可以将要复制的链表分为节点插入到每个原链表的节点后面，如图所示：

1.插入复制节点       

        想要实现如图所示效果，首先用malloc创建节点，然后后插入每个原节点的后面，这里要注意的是，应该先改变插入节点的next指针，防止因为覆盖导致原指针的next指针无法被找到。代码如下：

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 = copy->next;//通过赋值让cur继续往后走}

结束条件以cur为主体确定：cur走到空停止。

2.控制random

        通过后插节点解答的优越性就体现出来了，将难以寻找的random节点通过后插copy节点实现新的copy节点的random指针在原节点的random指针的下一个位置。代码实现如下：

cur = head;while(cur){struct Node* copy = cur->next;;if(cur->random == NULL){copy->random = NULL;}else{copy->random = cur->random->next;//此解法的优势所在}cur = copy->next;//cur往后走   }

3.将效果实现好的copy从原链表中拆解为独立的新链表（恢复原链表）

        在这里我们为了防止覆盖要多创建一个next指针存放节点位置，并定义头节点与尾指针来进行尾插的实现。循环的主体仍是cur。代码实现如下：

cur = head;struct Node* copytail = NULL, *copyhead = NULL;while(cur){struct Node* copy = cur->next;struct Node* next = copy->next;  if(copytail == NULL){copyhead = copytail = copy;}else{copytail->next = copy;copytail = copytail->next;}cur->next = next;//恢复原链表cur = next;}return copyhead;

        像这样，通过化繁为简的方法将复杂的问题分为三块较为简单的函数，就可以解决问题了。

最后，我们将代码整合起来，即为：

/*** 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 = copy->next;//copy往后走}//控制randomcur = head;while(cur){struct Node* copy = cur->next;;if(cur->random == NULL){copy->random = NULL;}else{copy->random = cur->random->next;//此解法的优势所在}cur = copy->next;//cur往后走   }//将copy节点尾插到新链表中cur = head;struct Node* copytail = NULL, *copyhead = NULL;while(cur){struct Node* copy = cur->next;struct Node* next = copy->next;  if(copytail == NULL){copyhead = copytail = copy;}else{copytail->next = copy;copytail = copytail->next;}cur->next = next;//恢复原链表cur = next;}return copyhead;
}