复杂链表的复制

前言

我们常见的链表中一般有3种类型的指针：指向下一个节点、指向上一个节点、尾节点指向头节点。在复杂链表中，每个节点除了拥有指向下一个节点的指针外，还会有一个指针用于指向链表中的任意节点或者null。本文就跟大家分享下如何复制一个复杂链表，欢迎各位感兴趣的开发者阅读本文。

实现思路

相信大多数看到这个问题的第一反应是把这个复制过程分成两步：

遍历原始链表，复制每个节点。
为复制链表设置每个节点的sibling指针。

假设原始链表中某个节点N的sibling指针指向节点S，由于S在链表中可能在N的前面也可能在N的后面。所以要定位S的位置就需要从原始链表的头节点开始找。

如果从头节点开始沿着next指针经过s步找到了了节点S，那么在复制链表上节点N’的sibling指针离复制链表的头节点的距离也是沿着next指针走s步。用这种方法我们就可以为复制链表上的每个节点设置sibling指针。

(如下图所示：节点1与节点2的sibling指针设置过程)。

那么，对于一个含有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'表示复制后的节点，做完这步操作后，链表的结构如下图所示。

第二步我们设置复制出来的节点的sibling指针，假设原始链表上的N的sibling指向节点S，那么（如下图所示）：

其对应复制出来的N’是N的next指针指向的节点(N->N')
同样的，S’也是S的next指针指向的节点(S->S')

进行到这里，相信大家已经看出规律了，上图的长链表中：奇数位置的节点是原始链表，偶数位置的节点是复制出来的节点。

第三步我们把长链表拆分成两个链表：

奇数位置的节点用next指针连接起来就为原始链表
偶数位置的节点用next指针连接起来就为复制出来的链表

我们将三步结合起来，就是复制链表的完整过程，做到了不使用额外的空间用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);

执行结果如下所示，正确的复制了链表出来。

示例代码

本文用到的代码完整版请移步：

写在最后

至此，文章就分享完毕了。

我是神奇的程序员，一位前端开发工程师。

如果你对我感兴趣，请移步我的个人网站，进一步了解。

文中如有错误，欢迎在评论区指正，如果这篇文章帮到了你，欢迎点赞和关注😊
本文首发于神奇的程序员公众号，未经许可禁止转载💌