前言
我们常见的链表中一般有3种类型的指针：指向下一个节点、指向上一个节点、尾节点指向头节点。在复杂链表中，每个节点除了拥有指向下一个节点的指针外，还会有一个指针用于指向链表中的任意节点或者null。本文就跟大家分享下如何复制一个复杂链表，欢迎各位感兴趣的开发者阅读本文。
实现思路
相信大多数看到这个问题的第一反应是把这个复制过程分成两步：
- 遍历原始链表，复制每个节点。
- 为复制链表设置每个节点的sibling指针。
假设原始链表中某个节点N的sibling指针指向节点S，由于S在链表中可能在N的前面也可能在N的后面。所以要定位S的位置就需要从原始链表的头节点开始找。
如果从头节点开始沿着next指针经过s步找到了了节点S，那么在复制链表上节点N'的sibling指针离复制链表的头节点的距离也是沿着next指针走s步。用这种方法我们就可以为复制链表上的每个节点设置sibling指针。
(如下图所示：节点1与节点2的sibling指针设置过程)。
image-20221201204750352
那么，对于一个含有n个节点的链表，定位每个节点的sibling指针都需要从链表头节点开始经过O(n)步才能找到，因此这种方法总的时间复杂度是O(n^2)。
经过观察后，上述方法的时间主要花费在定位节点的sibling指针上，这一部分能否优化呢？聪明的开发者可能已经想到在第一步遍历链表的时候，用一个HashMap把包含有sibling指针的节点一一对应存储起来。第二步在设置sibling指针的时候，只需要O(1)的时间即可从HashMap中找到当前节点对应的值。
我们用空间换取了时间，一个含有n个节点的链表，我们需要一个大小为O(n)的HashMap。时间复杂度降到了O(n)。那么，我们能否在不使用辅助空间的情况下实现O(n)的时间效率呢？
我们再来换种思路，第一步在复制节点的时候，把复制后的节点跟到原始节点之后，即A->A'->B...，我们用N'表示复制后的节点，做完这步操作后，链表的结构如下图所示。
image-20221201214026229
第二步我们设置复制出来的节点的sibling指针，假设原始链表上的N的sibling指向节点S，那么（如下图所示）：
- 其对应复制出来的N'是N的next指针指向的节点(
N->N') - 同样的，S'也是S的next指针指向的节点(
S->S')
image-20221201223444080
进行到这里，相信大家已经看出规律了，上图的长链表中：奇数位置的节点是原始链表，偶数位置的节点是复制出来的节点。
第三步我们把长链表拆分成两个链表：
- 奇数位置的节点用next指针连接起来就为原始链表
- 偶数位置的节点用next指针连接起来就为复制出来的链表
image-20221201225759588
我们将三步结合起来，就是复制链表的完整过程，做到了不使用额外的空间用O(n)的时间复杂度解决了此问题。
实现代码
捋清楚思路后，接下来我们来看下每一步的代码实现。
复制节点
遍历链表节点，对每个节点进行复制，用next指针连接N与N'节点。
function cloneNodes(pHead: complexListNodeType): void { let pNode: complexListNodeType | undefined = pHead; while (pNode != null) { // 复制当前节点，创建新节点:a' const pCloned: complexListNodeType = { value: pNode.value, next: pNode.next, sibling: null }; // 原始节点的指针指向复制出来的新节点上: a->a' pNode.next = pCloned; // 继续遍历原始节点的下一个节点: a = b pNode = pCloned.next; } }
复制sibling指针
遍历链表节点，获取N的next指针指向的N'节点，如果节点N有sibling指针，则取出其sibling指针的next指针指向的节点(S')，将N'的sibling指针指向S'。
function connectSiblingNodes(pHead: complexListNodeType) { // 获取节点N' let pNode: complexListNodeType | undefined = pHead; while (pNode != null) { const pCloned: complexListNodeType | undefined = pNode.next; if (pNode.sibling != null && pCloned != null) { // N'->S' pCloned.sibling = pNode.sibling.next; } if (pCloned != null) { pNode = pCloned.next; } } }
拆分长链表
遍历链表节点，声明两个指针分别指向原始节点与复制后的节点，逐步向后探索，直至将所有复制后的节点都提取出来。
function reconnectNodes(pHead: complexListNodeType) { let pNode: complexListNodeType | undefined = pHead; let pClonedHead: complexListNodeType | null | undefined = null; let pClonedNode: complexListNodeType | null | undefined = null; // 节点置换 // N' = N.next // N = N'.next if (pNode != null && pNode.next) { pClonedHead = pClonedNode = pNode.next; pNode.next = pClonedNode.next; pNode = pNode.next; } while (pNode != null && pClonedNode) { pClonedNode.next = pNode.next; pClonedNode = pClonedNode.next; if (pClonedNode) { pNode.next = pClonedNode.next; } pNode = pNode.next; } return pClonedHead; }
组合起来解决问题
接下来，我们只需要把三个函数组合起来即可解决这个问题。
export function copyComplexLinkedList( linkedList: complexListNodeType ): complexListNodeType | null { // 复制每一个节点紧跟其后: a->a'->b->b'->...n' cloneNodes(linkedList); // 复制sibling节点 connectSiblingNodes(linkedList); // 拆出复制好的链表 return reconnectNodes(linkedList); }
测试用例
我们用文章中列举的例子来校验下上述代码能否正确解决问题。
const complexLinkedList: complexListNodeType = { value: 1, next: { value: 2, next: { value: 3, next: { value: 4, next: { value: 5 } } } } }; // 设置sibling指针 insertSiblingNode(complexLinkedList, 1, 3); insertSiblingNode(complexLinkedList, 2, 5); insertSiblingNode(complexLinkedList, 4, 2); const result = copyComplexLinkedList(complexLinkedList); console.log("复制出来的链表", result);
执行结果如下所示，正确的复制了链表出来。
image-20221202214706985
image-20221202214846526
示例代码
本文用到的代码完整版请移步：
- CopyComplexLinkedList.ts
- CopyComplexLinkedList-test.ts
写在最后
至此，文章就分享完毕了。
我是神奇的程序员，一位前端开发工程师。
如果你对我感兴趣，请移步我的个人网站，进一步了解。
- 公众号无法外链，如果文中有链接，可点击下方阅读原文查看😊
