侧边栏壁纸
博主头像
神奇的程序员

今天的努力只为未来

  • 累计撰写 158 篇文章
  • 累计创建 25 个标签
  • 累计收到 84 条评论

目 录CONTENT

文章目录

复杂链表的复制

神奇的程序员
2022-12-02 / 0 评论 / 2 点赞 / 272 阅读 / 3,407 字 正在检测是否收录...

前言

我们常见的链表中一般有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

示例代码

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

写在最后

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

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

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

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

评论区