前端进阶算法4：链表原来如此简单(+leetcode刷题）-低调大师

前端进阶算法4：链表原来如此简单(+leetcode刷题）

2021-05-17 614

引言

链表相对于数组来说，要复杂的多，首先，链表不需要连续的内存空间，它是由一组零散的内存块透过指针连接而成，所以，每一个块中必须包含当前节点内容以及后继指针。最常见的链表类型有单链表、双链表以及循环链表。

学习链表最重要的是 多画图多练习 ，没有捷径可循，在遇到链表问题时，瓶子君总结了一下，可以按照以下五步骤：

确定解题的数据结构：单链表、双链表或循环链表等
确定解题思路：如何解决问题
画图实现：画图可以帮助我们发现思维中的漏洞（一些思路不周的情况）
确定边界条件：思考解题中是否有边界问题以及如何解决
代码实现：解题完成

本文会给常用链表（单链表、双链表以及循环链表）的基本操作已经代码实现，并给出实现思路，这些都是链表解题的基石，请务必掌握！

最后附赠一道 leetcode 题目！

下面开始本节的学习吧！！！

一、单链表

img

单链表结构：

function List () {
  // 节点
  let Node = function (element) {
    this.element = element
    this.next = null
  }
  // 初始头节点为 null
  let head = null

  // 链表长度
  let length = 0
  // 操作
  this.getList = function() {return head}
  this.search = function(list, element) {}
  this.append = function(element) {}
  this.insert = function(position, element) {}
  this.remove = function(element){}
  this.isEmpty = function(){}
  this.size = function(){}
}

1. 追加节点：

确定解题的数据结构：单链表

确定解题思路：初始化一个节点（待追加节点），遍历到链尾，在尾节点后插入该节点

画图实现：

确定边界条件：当链表为 null ，直接将 head 指向待插入节点，不需要遍历

代码实现：

function append (element) {
  let node = new Node(element),
      p = head
  if (!head){
    head = node
  } else {
    while (p.next) {
      p = p.next
    }
    p.next = node
  }
  length += 1
}

// 测试
let list = new List()
for(let i = 0; i < 5; i+=1) {
  list.append(i)
}

解题完成

2. 查找：

确定解题的数据结构：单链表

确定解题思路：遍历单链表，判断节点值是否等于待查找值，相等则返回 true ，否则继续遍历下一个节点，直到遍历完整个链表还未找到，则返回 false

画图实现：很简单，读者可以尝试画一下

确定边界条件：当链表为 null ，可直接返回 false

代码实现：

// 判断链表中是否存在某节点
function search(element) {
  let p = head
  if (!p) return false
  while(p) {
    if (p.element === element) return true
    p = p.next
  }
  return false
}

// 测试
list.search(4) // true
list.search(11) // false

解题完成

3. 在 position 位置插入：

确定解题的数据结构：单链表

确定解题思路：初始化一个节点（待插入节点 node ），遍历到 position 前一个位置节点，在该节点后插入 node

画图实现：

img

确定边界条件：

当 position 为 0 时，直接将插入节点 node.next 指向 head ， head 指向 node 即可，不需要遍历
当待插入位置 position < 0 或超出链表长度 position > length ，都是有问题的，不可插入，此时直接返回 null ，插入失败

代码实现：

// 插入 position 的后继节点
function insert (position, element) {
  // 创建插入节点
  let node = new createNode(element)
  if (position >= 0 && position <= length) {
    let prev = head,
        curr = head,
        index = 0
    if(position === 0) {
      node.next = head
      head = node
    } else {
      while(index < position) {
        prev = curr
        curr = curr.next
        index ++
      }
      prev.next = node
      node.next = curr
    }
    length += 1
  } else {
    return null
  }
}

// 测试
list.insert(10)

解题完成

4. 删除：

确定解题的数据结构：单链表

确定解题思路：遍历单链表，找到待删除节点，删除

画图实现：

img

确定边界条件：当链表为 null ，直接返回

代码实现：

// 删除值为 element 节点
function remove (element) {
  let p = head, prev = head
  if(!head) return
  while(p) {
    if(p.element === element) {
      p = p.next
      prev.next = p
    } else {
        prev = p
        p = p.next
    }
  }
}

解题完成

5. 复杂度分析：

查找：从头节点开始查找，时间复杂度为 O(n)

插入或删除：在某一节点后插入或删除一个节点（后继节点）的时间复杂度为 O(1)

链表五步骤是不是很好用，下面看一下双链表

二、双链表

顾名思义，单链表只有一个方向，从头节点到尾节点，那么双链表就有两个方向，从尾节点到头节点：

function DoublyLinkedList() {
    let Node = function(element) {
        this.element = element
        // 前驱指针
        this.prev = null
        // 后继指针
        this.next = null
    }
    // 初始头节点为 null
    let head = null
    // 新增尾节点
    let tail = null

    // 链表长度
    let length = 0
    // 操作
    this.search = function(element) {}
    this.insert = function(position, element) {}
    this.removeAt = function(position){}
    this.isEmpty = function(){ return length === 0 }
    this.size = function(){ return length }
}

1. 在 position 位置插入节点：

确定解题的数据结构：双链表

确定解题思路：初始化一个节点（待插入节点 node ），遍历链表到 position 前一个位置节点，在该节点位置后插入 node

画图实现：

确定边界条件：

当待插入位置 position < 0 或超出链表长度 position > length ，都是有问题的，不可插入，此时直接返回 null ，插入失败

代码实现：

// 插入 position 的后继节点
function insert (position, element) {
  // 创建插入节点
  let node = new Node(element)
  if (position >= 0 && position < length) {
    let prev = head,
        curr = head,
        index = 0
    if(position === 0) {
      // 在第一个位置添加
        if(!head) { // 注意这里与单链表不同
          head = node
          tail = node
        } else {
          // 双向
          node.next = head
          head.prev = node
          // head 指向新的头节点
          head = node
        }
    } else if(position === length) {
      // 插入到尾节点
      curr = tial
      curr.next = node
      node.prev = curr
      // tail 指向新的尾节点
      tail = node
    } else {
      while(index < position) {
        prev = curr
        curr = curr.next
        index ++
      }
      // 插入到 prev 后，curr 前
      prev.next = node
      node.next = curr
      curr.prev = node
      node.prev = prev
    }
    length += 1
    return true
  } else {
    return false
  }
}

// 测试
list.insert(10)

解题完成

2. 删除：

确定解题的数据结构：双链表

确定解题思路：遍历双链表，找到待删除节点，删除

画图实现：

确定边界条件：当链表为 null ，直接返回

代码实现：

// 删除 position 位置的节点
function removeAt (position) {
  if (position >= 0 && position < length && length > 0) {
    let prev = head,
        curr = head,
        index = 0
    if(position === 0) {
      // 移除头节点
        if(length === 1) { // 仅有一个节点
          head = null
          tail = null
        } else {
          head = head.next
          head.prev = null
        }
    } else if(position === length-1) {
      // 移除尾节点
      curr = tial
      tail = curr.prev
      tail.next = null
    } else {
      while(index < position) {
        prev = curr
        curr = curr.next
        index ++
      }
      // 移除curr
      prev.next = curr.next
      curr.next.prev = prev
    }
    length -= 1
    return curr.element
  } else {
    return null
  }
}

解题完成

3. 查找：

双链表的查找和单链表类似，都是遍历链表，找到返回 true，找不到返回 false 。

4. 复杂度分析：

查找：查找前驱节点或后继节点时间复杂度为 O(1)，其它节点仍为 O(n)

插入或删除：插入或删除前驱节点或后继节点的时间复杂度都为 O(1)

> 三、循环单链表

循环单链表是一种特殊的单链表，它和单链表的唯一区别是：单链表的尾节点指向的是 NULL，而循环单链表的尾节点指向的是头节点，这就形成了一个首尾相连的环：

img

既然有循环单链表，当然也有循环双链表，循环双链表和双链表不同的是：

循环双链表的 tail.next（ tail 的后继指针）为 null ，循环双链表的 tail.next 为 head
循环双链表的 head.prev（ head 的前驱指针）为 null ，循环双链表的 head.prev 为 tail

这里以循环单列表为例

function CircularLinkedList() {
    let Node = function(element) {
        this.element = element
        // 后继指针
        this.next = null
    }
    // 初始头节点为 null
    let head = null

    // 链表长度
    let length = 0
    // 操作
    this.search = function(element) {}
    this.insert = function(positon, element) {}
    this.removeAt = function(position){}
    this.isEmpty = function(){ return length === 0 }
    this.size = function(){ return length }
}

1. 在 positon 后插入：

确定解题的数据结构：循环单链表

确定解题思路：初始化一个节点（待插入节点 node ），遍历到 position 前一个位置节点，在该节点后插入 node

画图实现：

确定边界条件：

当 position 为 0 时，需要遍历到尾节点，然后在尾节点后插入节点，并将 head 指向
当待插入位置 position < 0 或超出链表长度 position > length ，都是有问题的，不可插入，此时直接返回 null ，插入失败

代码实现：

// 插入 position 的后继节点
function insert (position, element) {
  // 创建插入节点
  let node = new createNode(element)
  if (position >= 0 && position <= length) {
    let prev = head,
        curr = head,
        index = 0
    if(position === 0) {
      // 与单链表插入不同的
      while(index < length) {
        prev = curr
        curr = curr.next
        index ++
      }
      prev.next = node
      node.next = curr
      head = node
    } else {
      while(index < position) {
        prev = curr
        curr = curr.next
        index ++
      }
      prev.next = node
      node.next = curr
    }
    length += 1
  } else {
    return null
  }
}

// 测试
list.insert(10)

解题完成

2. 查找：

和单链表类似，唯一不同的是：循环单链表的循环结束条件为 p !== head

// 判断链表中是否存在某节点
function search(element) {
  let p = head
  if (!p) return false
  // 和单链表的不同所在
  while(p !== head) {
    if (p.element === element) return true
    p = p.next
  }
  return false
}

// 测试
list.search(4) // true
list.search(11) // false

解题完成

3. 删除：

和单链表类似，唯一不同的是：循环单链表的循环结束条件为 p !== head

// 删除值为 element 节点
function remove (element) {
  let p = head, prev = head
  if(!head) return
  while(p !== head) {
    if(p.element === element) {
      p = p.next
      prev.next = p
    } else {
        prev = p
        p = p.next
    }
  }
}

解题完成

4. 复杂度分析

查找：循环链表从任一节点开始查找目标节点，时间复杂度为 O(n)

插入或删除：它和单链表一样，后继节点插入及删除的时间复杂度为 O(1)

> 四、leetcode21：合并两个有序链表

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

欢迎将答案提交到 https://github.com/sisterAn/JavaScript-Algorithms/issues/11，让更多人看到，瓶子君也会在明日放上自己的解答。

微信关注我们

原文链接：https://blog.51cto.com/u_15127654/2781974

转载内容版权归作者及来源网站所有！

低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。

【5.10-5.16】上周精彩回顾

优秀文章推荐 1、Dapr 运用之集成 Asp.Net Core Grpc 调用篇2、亚马逊商品销售数据爬虫分析报告 3、基本操作命令解析（续）4、SPA 路由三部曲之核心原理5、iOS逆向之对称算法（上） 6、批量修改linux用户密码脚本7、Redis事务不支持回滚，你居然还能进行事务控制，牛啊！8、组件 popup 设计和源码剖析9、如何让Spring MVC框架使用我们封装的JsonUtils实现消息的序列化和反序列化，并适配actuator框架10、sas神经网络：构建人工神经网络模型来识别垃圾邮件专题推荐 1、iOS逆向之对称算法2、Dapr 运用3、鸿蒙应用开发-DevEco Studio 模板体验4、温故Linux后端编程5、【技术原理】网络IO模型分析介绍6、开发成长之路7、CampusBulider（模模搭）学习笔记8、Spring+SpringMVC+MyBatis+easyUI整合基础篇9、Kubernetes集群实践活动及优化 1、恭祝2021年度51CTO技术博客大赛已经圆满结束！烦请获奖博主联系小助手vx：xiaozhu0264 或私聊领取奖品【获奖...

2021-05-17

702

简介数组、链表、栈、队列都是线性表，它表示的结构都是一段线性的结构，与之对应的就是非线性表，例如树、图、堆等，它表示的结构都非线性。本节主要介绍 JavaScript 数组，在开始本章节前，思考一个问题：我们知道在 JavaScript 中，可以在数组中保存不同类型值，并且数组可以动态增长，不像其它语言，例如 C，创建的时候要决定数组的大小，如果数组满了，就要重新申请内存空间。这是为什么喃？本节从 Chrome v8 源码角度回答这个问题，分为四个方面：数组基础入门 JavaScript 中，数组为什么可以保存不同类型？ JavaScript 中，数组是如何存储的喃？ JavaScript 中，数组的动态扩容与减容（ FastElements ）下面进入正题吧！（文末有惊喜）想要更多更快的学习本系列，可以关注公众号「前端瓶子君」和我的「Github：https://github.com/sisterAn/JavaScript-Algorithms」一、数组（基础）一种最基础的数据结构，每种编程语言都有，它编号从 0 开始，代表一组连续的储存结构，用来储存同一种类型的数...

2021-05-17

495

资源下载

更多资源

Mario

马里奥是站在游戏界顶峰的超人气多面角色。马里奥靠吃蘑菇成长，特征是大鼻子、头戴帽子、身穿背带裤，还留着胡子。与他的双胞胎兄弟路易基一起，长年担任任天堂的招牌角色。

Nacos

Nacos /nɑ:kəʊs/ 是 Dynamic Naming and Configuration Service 的首字母简称，一个易于构建 AI Agent 应用的动态服务发现、配置管理和AI智能体管理平台。Nacos 致力于帮助您发现、配置和管理微服务及AI智能体应用。Nacos 提供了一组简单易用的特性集，帮助您快速实现动态服务发现、服务配置、服务元数据、流量管理。Nacos 帮助您更敏捷和容易地构建、交付和管理微服务平台。

Spring

Spring框架（Spring Framework）是由Rod Johnson于2002年提出的开源Java企业级应用框架，旨在通过使用JavaBean替代传统EJB实现方式降低企业级编程开发的复杂性。该框架基于简单性、可测试性和松耦合性设计理念，提供核心容器、应用上下文、数据访问集成等模块，支持整合Hibernate、Struts等第三方框架，其适用范围不仅限于服务器端开发，绝大多数Java应用均可从中受益。

Sublime Text

Sublime Text具有漂亮的用户界面和强大的功能，例如代码缩略图，Python的插件，代码段等。还可自定义键绑定，菜单和工具栏。Sublime Text 的主要功能包括：拼写检查，书签，完整的 Python API ， Goto 功能，即时项目切换，多选择，多窗口等等。Sublime Text 是一个跨平台的编辑器，同时支持Windows、Linux、Mac OS X等操作系统。