当前位置 : 主页 > 编程语言 > c语言 >

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

来源:互联网 收集:自由互联 发布时间:2023-09-07
朋友们,晚上好!!今天,推出一篇单链表的随机指针问题!! 相较于之前的链表OJ题,本期的链表难度有所提升!! 下面请看题 : 有一个链表, 链表每个结点额外增加一个随机指针

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

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

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

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

如下图所示 :>

单链表进阶OJ版--->随机指针问题_分过程

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

那么, 具体实现的思路,有哪些呢?

大体上, 可以分为三点 :

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;
}

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

单链表进阶OJ版--->随机指针问题_分过程_02

首先是第一个步骤 :

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

附上图示样板 :

单链表进阶OJ版--->随机指针问题_单节点含有额外指针_04

之后是第二个步骤 :

单链表进阶OJ版--->随机指针问题_分过程_05

再附上图示样板 :

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

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

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

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

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

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

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

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

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

最后是第三个步骤 :

单链表进阶OJ版--->随机指针问题_单节点含有额外指针_07

再附上图示样板 :

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

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

单链表进阶OJ版--->随机指针问题_分过程_10

至此,本期讲解就到这里了!!

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

上一篇:利用win消息机制的木马
下一篇:没有了
网友评论