链表

1. 链表的基础知识

什么是链表：
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
链表由一个个结点组成，每个结点包括两个部分：

• 存储的数据域
• 存储下一个结点地址的指针域

一张图表示链表

链表的代码实现

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

2. 链表的使用

2.1插入结点

2.1.1顺序插入—— 添加到链表的尾部

const head = new ListNode(0)

// 插入节点
head.next = new ListNode(1)
head.next.next = new ListNode(2)
head.next.next.next = new ListNode(3)
console.log(head)
/**
  ListNode {
    val: 0,
    next: ListNode {
        val: 1,
        next: ListNode {
          val: 2,
        next: null
      } 
    }
  }
*/

同样的操作，优雅一点，封装一下

const head = new ListNode(0, new ListNode(1))

function insertToTail(list: ListNode | null, value: number) {
  if (!list) return new ListNode(value)
    let p = list
  while (p.next) {
    p = p.next
  }
  p.next = new ListNode(value)
}

// 调用一下
insertToTail(head, 2)

因为指针引用的原因，所以最后得到的 p 其实就是 list 这个链表的最后一位，所以最后 p.next = new ListNode(value) 其实就是给 list 的最后一个结点的 next 添加 new ListNode(value)。

2.1.2 中途插入

搞懂了上面的顺序插入，那么中途插入也很简单

// 题目要求：在链表中寻找到目标结点，然后在目标结点后面插入一个结点

const head = new ListNode(0, new ListNode(1))
/**
* 一般这种题是保证一定存在目标节点的
* @target 目标位置
* @node 在目标位置后面插入的结点
*/
function insertToTarget(list: ListNode, target: number, node: ListNode) {
    let p = list
  while (p) {
      if (p.val === target) {
        node.next = p.next // 将需要插入的结点的 next 设置为 目标结点 的 next
      p.next = node // 将 目标节点 的 next 设置为需要插入的节点
      return
    }
    p = p.next
  }
}

const node = new ListNode(3)

insertToTarget(head, 0, node)
console.log(head) // 简略表示为： 0, 3, 1

其他的复杂操作基本上都是基于此，理解了以后其实也没什么难的。

2.2 删除结点

玩会了插入节点，删除节点也很简单
删除头节点

// 简直送分有木有（注意值引用被改变的坑）
function removeHeadNode (head: ListNode | null) {
  if (!head) return null
  return head.next
}

// 偷一下懒，就不 new ListNode 了，直接用数组表示会简洁一些，也更直观
let head = [1, 2, 3]

head = removeHeadNode(head)
console.log(head) // [2, 3]

删除指定节点

function removeTargetHandle(head: ListNode | null, target: number) {
    if (!head || head.val === target) return null // 如果头结点就是目标结点，则直接处理掉
  let p = head
  while(p && p.next) {
    if (p.next.val === target) { // 每次找 next 的 val 来比较
        p.next = p.next.next // 找到则将 next 节点覆盖掉
      return head
    }
    p = p.next
  }
  return head
}

来点 leetcode 的题，删除排序链表中的重复元素

function deleteDuplicates(head: ListNode | null): ListNode | null {
  if(!head || !head.next) return head
  let p = head
  while(p && p.next) {
    if (p.val === p.next.val) {
      // 保留当前，去掉 next，指针仍为 head 中的元素
      // 注意上面提到的指针问题，p = p.next.next 将不会改变到 head
      p.next = p.next.next 
    } else {
      p = p.next
    }
  }
  return head
};

删除链表中的重复元素二

function deleteDuplicates(head: ListNode | null): ListNode | null {
  if (!head || !head.next) return head
  let ret = new ListNode(-1, head) // 创建空的头指针
  let slow = ret
  let fast = head
  while (fast && fast.next) {
    if (fast.next.val !== slow.next.val) { // 快慢指针的 next 元素值不相等时各跳一位
      fast = fast.next
      slow = slow.next
    } else {
      while(fast && fast.next && fast.next.val === low.next.val) { // 快慢指针的 next 相等时（前后比较）
        fast = fast.next
      }
      // 重点在这儿：跳过当前已知的重复元素 比如此时 fast 走到了 1 2 3 3(走到了第二个 3 的位置，后面还有 4 4 5)
      // 此时 slow 指向 2，那么 slow 的 next 指向 fast.next 就直接跳过了重复的 3
      slow.next = fast.next 
      fast = fast.next
    }
  }
  return ret.next
};

这一题重点标出来了，不理解可以画图来帮助自己理解

2.3 查找

环形链表

// 简单题，快慢指针搞定
function hasCycle(head: ListNode | null): boolean {
    if (!head) return false
  let slow = head
  let fast = head.next
  while(slow !== fast && slow && fast && slow.next && fast.next) {
      slow = slow.next
    fast = fast.next.next
  }
  // 到这里，可能是因为 slow 和 fast 相等
  if (slow !== fast) return false // 也有可能链表循环结束
  return true
};

环形链表II

function detectCycle(head: ListNode | null): ListNode | null {
    if (!head) return null
    let slow = head
    let fast = head.next
    while(slow !== fast && slow && fast && slow.next && fast.next) {
      slow = slow.next
      fast = fast.next.next
    }
    // 可能链表没环，也有可能链表有环
    if (slow !== fast) return null // 链表没环
    // 链表有环，重点在这儿
    // 以 head = [3,2,0,-4], pos = 1 为示例（值为2）
      // 快指针每次始终比慢指针多移动一步，快慢指针相交于值为 0 的位置
    // 相交点再移动一位到环点的距离与头结点到到环点的位置相等
    slow = head // 一个指针移动到头节点
    fast = fast.next // 一个指针移动到 next
    while(slow !== fast) {
        slow = slow.next
        fast = fast.next
    }
    return slow // 返回相遇的点
};