前端进阶之旅前端进阶之旅
基础篇
进阶篇
高频篇
精选篇
手写篇
原理篇
面经篇
自检篇
每日一题
  • 综合
    • 综合题型
    • 其他问题
    • 设计模式
    • 思维导图
    • 学习路线
  • 前端基础
    • HTTP
    • 浏览器
    • 计算机基础
  • 进阶学习
    • NPM工作流
    • Docker
    • Canvas
    • Node学习指南
    • 前端综合文章
  • 其他
    • Handbook
    • 职场话题
    • CSS可视化
小程序题库
公众号动态
博客动态
开发者导航
基础篇
进阶篇
高频篇
精选篇
手写篇
原理篇
面经篇
自检篇
每日一题
  • 综合
    • 综合题型
    • 其他问题
    • 设计模式
    • 思维导图
    • 学习路线
  • 前端基础
    • HTTP
    • 浏览器
    • 计算机基础
  • 进阶学习
    • NPM工作流
    • Docker
    • Canvas
    • Node学习指南
    • 前端综合文章
  • 其他
    • Handbook
    • 职场话题
    • CSS可视化
小程序题库
公众号动态
博客动态
开发者导航
  • React专栏

    • React组合式开发实战

      • 前端开发的四个时代
      • 企业管理系统的前世今生
      • 可视化页面搭建工具
      • 实战篇 01:开发前准备
      • 实战篇 02:项目脚手架
      • 实战篇 03:页面布局方案
      • 实战篇 04:权限管理机制
      • 实战篇 05:菜单匹配逻辑
      • 实战篇 06:消息通知设计
      • 实战篇 07:多语言支持
      • 继往开来:可视化页面搭建工具
    • React Hooks与Immutable实战

    • React SSR服务端渲染与同构实践

    • IM聊天系统前端开发实践

    • 微前端开发实战

    • React进阶实践

  • Vue专栏

  • 移动端专栏

  • Node专栏

  • 前端工程化专栏

  • 算法专栏

  • Typescript专栏

  • 其他专栏

完整面试题地址:
作者:程序员poetry
扫码关注作者公众号:「前端进阶之旅」 每天分享技术干货
前端进阶之旅公众号二维码

# 题目

输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),返回结果为复制后复杂链表的head。

# 思路

拆分成三步

1.复制一份链表放在前一个节点后面,即根据原始链表的每个节点N创建N,把N直接放在N的next位置,让复制后的链表和原始链表组成新的链表。

2.给复制的链表random赋值,即N.random=N.random.next。

3.拆分链表,将N`和N进行拆分,保证原始链表不受影响。

# 代码

    function Clone(pHead) {
      if (pHead === null) {
        return null;
      }
      cloneNodes(pHead);
      cloneRandom(pHead);
      return reconnetNodes(pHead);
    }

    function cloneNodes(pHead) {
      var current = pHead;
      while (current) {
        var cloneNode = {
          label: current.label,
          next: current.next
        };
        current.next = cloneNode;
        current = cloneNode.next;
      }
    }

    function cloneRandom(pHead) {
      var current = pHead;
      while (current) {
        var cloneNode = current.next;
        if (current.random) {
          cloneNode.random = current.random.next;
        } else {
          cloneNode.random = null;
        }
        current = cloneNode.next;
      }
    }

    function reconnetNodes(pHead) {
      var cloneHead = pHead.next;
      var cloneNode = pHead.next;
      var current = pHead;
      while (current) {
        current.next = cloneNode.next;
        current = cloneNode.next;
        if (current) {
          cloneNode.next = current.next;
          cloneNode = current.next;
        } else {
          cloneNode.next = null;
        }
      }
      return cloneHead;
    }
@前端进阶之旅: 代码已经复制到剪贴板

# 考察点

  • 链表
  • 复杂问题拆解
fe
基础篇
进阶篇
高频篇
精选篇
手写篇
原理篇
面经篇
自检篇
每日一题
  • 综合
    • 综合题型
    • 其他问题
    • 设计模式
    • 思维导图
    • 学习路线
  • 前端基础
    • HTTP
    • 浏览器
    • 计算机基础
  • 进阶学习
    • NPM工作流
    • Docker
    • Canvas
    • Node学习指南
    • 前端综合文章
  • 其他
    • Handbook
    • 职场话题
    • CSS可视化
小程序题库
公众号动态
博客动态
开发者导航
  • React专栏

    • React组合式开发实战

      • 前端开发的四个时代
      • 企业管理系统的前世今生
      • 可视化页面搭建工具
      • 实战篇 01:开发前准备
      • 实战篇 02:项目脚手架
      • 实战篇 03:页面布局方案
      • 实战篇 04:权限管理机制
      • 实战篇 05:菜单匹配逻辑
      • 实战篇 06:消息通知设计
      • 实战篇 07:多语言支持
      • 继往开来:可视化页面搭建工具
    • React Hooks与Immutable实战

    • React SSR服务端渲染与同构实践

    • IM聊天系统前端开发实践

    • 微前端开发实战

    • React进阶实践

  • Vue专栏

  • 移动端专栏

  • Node专栏

  • 前端工程化专栏

  • 算法专栏

  • Typescript专栏

  • 其他专栏