关于算法:小五的算法系列-链表

Hello, 各位怯懦的小伙伴, 大家好, 我是你们的嘴强王者小五, 身体健康, 脑子没病.

自己有丰盛的脱发技巧, 能让你一跃成为资深大咖.

一看就会一写就废是自己的宗旨, 菜到抠脚是自己的特点, 低微中透着一丝丝坚强, 傻人有傻福是对我最大的刺激.

欢送来到 小五 的算法系列 之链表.

前言

此系列文章以《算法图解》和《学习 JavaScript 算法》两书为外围，其余材料为辅助，并佐以笔者愚见所成。力求以简略、趣味的语言带大家领略这算法世界的微妙。

本文内容为链表。笔者将率领大家从 js 模仿其实现登程，逐渐变动以摸索链表的其它模式，最初附上几道习题加深了解及坚固所学。

链表在 JavaScript 中有一重要利用 — 原型链，文章传送门  👉   大话原型链。

链表简介

笔者从“什么是链表”及“链表用来干什么”来给大家文言文言

🦥 什么是链表

链表就像寻宝游戏，宝物藏在小岛各处。游戏开始时会失去一条线索，通过手中线索去寻找下一个宝物的地点，顺次类推。

由此咱们总结下链表的特点:

• 宝物扩散在小岛各处 – 链表中的元素在内存中的存储地位并不间断
• 通过线索确定下一个地点 – 每个节点由存储元素自身及指向下一元素的指针组成，无奈越过某一节点达到下一节点

🦥 用来干什么

用来存储数据，此时你小小的脑袋上是不是有大大的问号，存储数据为什么不必数组呢?

咱们来联合各自特点比对下两种数据结构的优缺点:

👺 数组存储地位间断，而链表不间断

如果在数组两头插入一个元素会怎么 🤔 数组是间断的，就像插队一样，其余人都要向后一位；而链表存储不间断，插入时其余元素无需变动，删除同理；

故可得出结论：插入或删除元素时，链表比数组更有劣势

👺 数组间接拜访元素，而链表通过指针寻找元素

因数组存储间断，咱们可间接通过下标对其拜访；而链表则须要从表头开始逐个寻找，直至找到；

故可得出结论：查找元素时，数组比链表更有劣势

链表实现

👇 咱们接下来用 js 模仿一个链表，并为其增加如下办法：

• append(element)：向链表尾部追加新元素
• insert(element, position)：向链表特定地位插入新元素
• remove(element)：从链表中移除某一元素
• indexOf(element)：返回元素在链表中的索引, 若没有该元素则返回 -1
• removeAt(position)：从链表特定地位移除一个元素
• isEmpty()：链表中是否存在元素
• size()：链表中元素个数

对链表而言，无论是插入操作还是删除操作，均是扭转 next 指针指向的过程。

🦥 构造

首先咱们来定义下链表中的节点，应蕴含其元素自身 element 及指向下一节点的指针next

class Node<T> {
  element: T | null;
  next: Node<T> | null;

  constructor(element: T | null) {
    this.element = element;
    this.next = null;
  }
}

在来明确下链表构造，其须要有一个头部节点head，及一个记录长度的length

class LinkedList<T> {
  head: Node<T> | null = null;
  length = 0;
}

🦥 append(element)

若空，则其为头部节点；若非空，则其为链表尾部节点；

append(element: T) {let node = new Node<T>(element);

  if (!this.head) {this.head = node;} else {
    let current = this.head;
    while (current.next) {current = current.next;}
    current.next = node;
  }

  this.length++;
}

🦥 insert(element, position)

找到插入地位，更改 next 指向

• position = 0，node.next -> head
• position > 0，previous.next -> node, node.next -> current

insert(element: T, position: number) {if (position < 0 || position > this.length) return false;
  
  let node = new Node<T>(element);
  let index = 0;
  let current = this.head;
  let previous: Node<T> | null = null;

  if (position === 0) {
    node.next = this.head;
    this.head = node;
  } else {while (current && index++ < position) {
      previous = current;
      current = current.next;
    }
    (previous as Node<T>).next = node;
    node.next = current;
  }

  this.length++;
  return true;
}

🦥 removeAt(position)

思路同insert，找到插入地位，更改 next 指向

• position = 0，head -> head.next
• position > 0，previous.next -> current.next

removeAt(position: number) {if (!this.head || position < 0 || position >= this.length) return false;

  let index = 0;
  let current: Node<T> | null = this.head;
  let previous: Node<T> | null = null;

  if (position === 0) {this.head = this.head.next;} else {while (current && index++ < position) {
      previous = current;
      current = current.next;
    }
    (previous as Node<T>).next = current?.next || null;
  }

  this.length--;
  return true;
}

🦥 indexOf(element)

从头遍历链表即可

indexOf(element: T) {
  let current = this.head;
  let index = 0;

  while (current) {if (typeof current.element === 'object') {if (JSON.stringify(element) === JSON.stringify(current.element)) return index;
    } else {if (element === current.element) return index;
    }

    current = current.next;
    index++;
  }

  return -1;
}

🦥 remove(element)

整合 removeAt 和indexOf即可

remove(element: T) {let position = this.indexOf(element);
  return this.removeAt(position);
}

双向链表

字面意思阐明所有，一个连贯为双向的链表；可抉择“从头遍历至尾”亦或“从尾遍历至头”；

故咱们为 Node 类追加一个 prev 指针，为链表减少一个 tail 属性，改写以下三个办法append、insert、removeAt

🦶tips：只有留神好其指针的连贯即可，切莫丢三落四只连贯了一个方向

🦥 append(element)

• 若为空，则 head = node、tail = node
• 若非空，则 tail.next = node，node.prev = tail；而后更新 tail 即可

append(element: T) {let node = new Node<T>(element);

  if (!this.head || !this.tail) {
    this.head = node;
    this.tail = node;
  } else {
    this.tail.next = node;
    node.prev = this.tail;
    this.tail = node;
  }

  this.length++;
}

🦥 insert(element, position)

• 插入头部或尾部，思路同追加元素，思考好边界值即可
• 插入两头，next 链：prevNode.next = node -> node.next = nextNode；prev 链：nextNode.prev = node -> node.prev = prevNode；

insert(element: T, position: number) {if (position < 0 || position > this.length) return false;

  let node = new Node<T>(element);
  
  if (position === 0) {if (this.head) {
      this.head.prev = node;
      node.next = this.head;
      this.head = node;
    } else {
      this.head = node;
      this.tail = node;
    }
  }
  
  else if (position === this.length) {(this.tail as Node<T>).next = node;
    node.prev = this.tail;
    this.tail = node;
  }
  
  else {
    let current = this.head;
    let previous: Node<T> | null = null;
    let index = 0;

    while (current && index++ < position) {
      previous = current;
      current = current.next;
    }

    (previous as Node<T>).next = node;
    node.next = current;
    (current as Node<T>).prev = node;
    node.prev = previous;
  }

  this.length++;
}

🦥 removeAt(position)

思路根本和 insert 统一

• 若链表仅有一个节点，头尾节点别离赋 null
• 删除头部：head = head.next、head.prev = null，尾部同理
• 删除两头 preNode.next = nextNode、nextNode.prev = preNode

removeAt(position: number) {if (!this.head || position < 0 || position >= this.length) return false;

  if (position === 0) {if (this.length === 1) {
      this.head = null;
      this.tail = null;
    } else {
      this.head = this.head.next;
      (this.head as Node<T>).prev = null;
    }
  }

  else if (position === this.length - 1) {this.tail = (this.tail as Node<T>).prev;
    (this.tail as Node<T>).next = null;
  }

  else {
    let current: Node<T> | null = this.head;
    let previous: Node<T> | null = null;
    let index = 0;
    while (current && index++ < position) {
      previous = current;
      current = current.next;
    }
    if (!previous || !current) return false;
    previous.next = current.next;
    (current.next as Node<T>).prev = previous;
  }

  this.length--;
  return true;
}

循环链表

正如其名，首尾相连即造成了循环链表 tailNode.next = head；实现时留神好边界值的解决即可，尤其是波及首尾元素的解决；思维上与上文实现基本一致，大家无妨入手试试看。

👺 双脚奉上单循环链表的代码连贯：单循环链表

小试牛刀

以下题目均来自 LeetCode，笔者会为每道题目提供一种解题思路；此思路绝非最佳，欢送各位看官积极思考，并留下本人的独特见解。

鉴于题干较长，请点击题目查看具体题目。

下文所有 ListNode 格局如下:

class ListNode {
  val: number
  next: ListNode | null
  constructor(val?: number, next?: ListNode | null) {this.val = (val === undefined ? 0 : val)
    this.next = (next === undefined ? null : next)
  }
}

LeetCode 141. 环形链表

👺 题目简述

入参为头节点，判断是否可成环。

👺 题目剖析

判断是否成环，第一想法为借用长度，若超出长度仍可循环，则有环。

let index = 0;
let current = head;
while (current) {if (index > size) return true;
  current = current.next;
  index++;
}
return false;

但此题入参仅有头节点，得换个思路；一个指针必然行不通，没有突破循环的条件，有环岂不是死循环了；那咱们借助两个指针，一快一慢，想不明确的话能够类比下时钟或者跑步压圈，如若有环，一快一慢必然相遇。

👺 代码实现

const hasCycle = (head: ListNode | null): boolean => {
  let slow = head;
  let fast = head;
  while (slow && fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) {return true;}
  }
  return false;
};

LeetCode 2. 两数相加

👺 题目简述

下图为两个逆序存储的链表，代表：342 + 465 = 807

入参：两个链表的头部 l1、l2，求新生成链表 (sum 的链表模式)

👺 题目剖析

笔者看到此题，首先想到的是，别离遍历两个链表，取到对应数字，相加后存入新链表；当笔者兴致冲冲的提交后，大数了，若在我的项目中能够 big.js 等解决下大数，这毕竟是练习题，咱们尝试换个思路。

遍历 l1 -> 获取 342
遍历 l2 -> 获取 465
342 + 465 = 807
807 存入链表 7 -> 0 -> 8

这就是一个手写加法运算的过程，咱们按位相加，2 + 5 = 7，4 + 6 = 10 即 0 进位 1，3 + 4 + 进位 1 = 8

• 遍历 l1、l2，按位相加
• 新增变量代表是否进位，若进位则加 1
• 留神最初若仍旧有进位，需补 1，如:

89 + 13 = 102
-------------
9 8
3 1
-----
2 0 1

👺 代码实现

const addTwoNumbers = (
  l1: ListNode | null,
  l2: ListNode | null,
): ListNode | null => {
  let current1 = l1;
  let current2 = l2;
  let carryOver = 0; // 进位
  let sum: ListNode = new ListNode(); // sum 链, 给个默认头部, 最初取 next 即可
  let current: ListNode | null = sum;

  while (current1 || current2) {
    // 两链表未必等长 如 999 + 1
    let currentSum = (current1?.val || 0) + (current2?.val || 0) + carryOver;
    carryOver = 0;

    if (currentSum >= 10) {
      carryOver = 1;
      currentSum -= 10;
    }

    current.next = new ListNode(currentSum);

    current1 = current1?.next || null;
    current2 = current2?.next || null;
    current = current.next;
  }

  if (carryOver > 0) current.next = new ListNode(carryOver);

  return sum.next;
};

LeetCode 24. 两两替换链表中的节点

👺 题目简述

给定一个链表，两两替换其中相邻的节点，并返回替换后的链表

入参：链表头节点

👺 题目剖析

链表问题实质都是拨弄指针的问题，以 1、3、4 两两调换为例

[1, next: 3] [3, next: 4], [4, next: null]
------------------------------------------
[1, next: 3] -> [1, next: 4]
[4, next: null] -> [4, next: 3]
[3, next: 4 -> [3, next: null]

留神下边界值，首次循环时解决的只有两个节点，且需记录新的 head 值

👺 代码实现

const swapPairs = (head: ListNode | null): ListNode | null => {
  let previous: ListNode | null = null;
  let current = head;
  let index = 0; // 记录是否为首次循环
  while (current && current.next) {
    previous = current;
    current = current.next;

    if (index === 0) {
      previous.next = current.next;
      current.next = previous;
      head = current; // 替换后扭转头部的值
    }

    if (index > 0 && current.next) {
      let node = current;
      current = current.next;
      node.next = current.next;
      previous.next = current;
      current.next = node;
    }

    current = current.next;
    index++;
  }

  return head;
}

后记

🔗 本文代码 Github 链接：链表

🔗 本系列其它文章链接：起航篇 – 排序算法、栈与队列