单链表进阶OJ版--->随机指针问题

朋友们，晚上好！！今天，推出一篇单链表的随机指针问题！！

相较于之前的链表OJ题，本期的链表难度有所提升！！下面请看题 :>

有一个链表， 链表每个结点额外增加一个随机指针 random ，并且随机指针可以指向链表的任何结点以及空结点

至于本题的要求是 ： 复制带随机指针的链表

如下图所示 :>

本题的难度，大致在于 随机指针的指向不好把控 ！！

那么， 具体实现的思路，有哪些呢？

大体上， 可以分为三点 :

1.拷贝原链表的每个结点，连接到原节点的后面

2.将随机指针的拷贝值连接在原链表随机值的下一个位置（至于原因，稍后解释）

3.拆解链表， 将新的链表与旧链表分离开

大体上，思路就这些了。现在，开始我们的代码实现吧！！

/*
typedef int SLTDataType;

typedef struct SListNode
{
	SLTDataType data;
  struct SListNode* next;
  struct SListNode* random;
}SLTNode;

*/

SLTNode* copyRandomList(SLTNode* phead)
{
	SLTNode* cur = phead;
  //1.拷贝原链表的每个结点，连接到原节点的后面
  while(cur)
  {
  	SLTNode* next = cur ->next;
    
    SLTNode* copy = (SLTNode*)malloc(sizeof(SLTNode));
    copy ->data = cur ->data;
    
    //插入链接
    cur ->next = copy;
    copy ->next = next;
    
    //迭代
    cur = next;
  }
  
  //将随机指针的拷贝值连接在原链表随机值的下一个位置
  cur = phead;
  while(cur)
  {
  	SLTNode* copy = cur ->next;
    
    if(cur ->random == NULL)
    {
      copy ->random = NULL;
    }
    else
    {
    	copy ->random = cur ->random ->next;
    }
    
    //迭代
    cur = cur ->next ->next;
  }
  
  //3.拆解链表， 将新的链表与旧链表分离开
  cur = phead;
  SLTNode* copyHead = NULL, *copyTail = NULL;
  while(cur)
  {
  	SLTNode* copy = cur ->next;
    
    if(copyTail == NULL)
    {
    	copyHead = copyTail = copy;
    }
    else
    {
    	copyTail ->next = copy;
      copyTail = copyTail ->next;
    }
    
    //恢复旧链表
    cur ->next = copy ->next;
    cur = next;
  }
  return copyHead;
}

为了各位好友，方便观看，特别附上有色彩观感的代码图样 ：

首先是第一个步骤 ：

附上图示样板 ：

之后是第二个步骤 ：

再附上图示样板 ：

现在解析 --->“精华所在”

请注意看上图所示的橙色线条，如何将新结点的 random 链接在 指定 新节点的正确位置，也就是同旧链表的链接方式相同！！

比如，将新节点的 13 的 random 链接在 7 上如何操作，能符合原先链表的链接

答案是 ：先思考 旧链表与新链表之间的联系。而由第一个步骤，我们知道，新链表的每个节点位置在原节点的后面！！如此，便确立了突破口！！

现在看看，旧链表的 13 的 random 是如何链接在 7 上面的，显然是 “cur -> random”

这句代码 就代表了 13 指向了 7 这个位置，而 7 又通过 一个 “next”指向了 新节点 7 的位置

如此，我们不难理解，代码“copy ->random = cur -> random ->next”

即新节点 13 是如何将随机指针 random 指向 7 的位置了！！

最后是第三个步骤 ：

再附上图示样板 ：

至此，本期讲解就到这里了！！

感谢好友阅读！！愿共同进步！！