单链表进阶OJ版如何实现高效操作？

本文共计1203个文字，预计阅读时间需要5分钟。

亲爱的朋友们，晚上好！🌙🌟

今天，我们来探讨一个单链表的随机指针问题！🔍

相较于之前的链表OJ题，本期的链表难度有所提升！💪

下面是题目内容：

有一个链表，链表每个节点除了有值和下一个节点的指针外，还有一个随机指针指向链表中的任意节点，包括它自己。

请实现一个函数，对链表进行遍历，并返回链表的头节点。

题目要求：

1.有一个链表，链表每个节点包含一个整数值和两个指针，一个指向下一个节点，另一个指向链表中的任意节点（包括它自己）。

2.实现一个函数，对链表进行遍历，并返回链表的头节点。

请看题：📚

输入：链表节点

输出：链表头节点

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

相较于之前的链表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 的位置了！！

最后是第三个步骤 ：

再附上图示样板 ：

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

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