11-01 12:26 阅读 102

关注

算法基础知识学习笔记-链表

一. 关于链表

链表由一系列节点组成，每个节点都包含了data（数据）和next（下一个节点的指针）组成，下图就是一个简单的链表示意图

• 关于节点的代码

class ListNode {
    constructor(val) {
        this.val = val;
        this.next = null;
    }
}复制代码

• 组成链表

let node1 = new ListNode(1)
let node2 = new ListNode(2)
let node3 = new ListNode(3)
node1.next = node2
node2.next = node3
console.log(node1) // head复制代码

二. 做题笔记

1. 翻转链表 （力扣206题）

• 迭代翻转 （思路：遍历每个节点，把当前节点的指针指向前一个）

  function reverse (head) {
      if (!head || !head.next) return head
      let curr = head, // 当前要遍历的节点
      pre = null // 当前节点的前一个节点
      while (curr) {
          let next = curr.next // 暂存当前节点的下一个节点
          curr.next = pre // 当前节点的指针指向前一个
          pre = curr // 前一个节点后移一位
          curr = next // 当前节点后移一位
      }
      // 循环终止，curr为null，curr的前一位即pre是新的head
      return pre
  };复制代码

• 递归翻转（思路：从后往前操作）

  function reverse (head) {
      if (!head || !head.next) return head
      let tail = head.next // 下一个节点
      let newHead = reverse(tail)
      head.next = tail.next // 这句特别不好理解
      tail.next = head // 下一个节点的指针指向自己
      return newHead
  }复制代码

  // 比较好理解的迭代代码
  function reverse (head) {
      function reverseFn (head, pre){
          if(!head) return pre
          let tail = head.next // 缓存下一个节点
          head.next = pre // 翻转
          return reverse(tail, head)
      }
      return reverseFn(head, null)
  }复制代码

1-1. 翻转链表延伸

• 翻转从头到固定位数的节点

  function reverseN (head, n) { // 多一个参数
       if (!head || !head.next) return head
       if (n === 1) return head // 与递归翻转不一样的地方
       let tail = head.next
       let newHead = reverse(tail, n - 1) // 多一个参数
       head.next = tail.next
       tail.next = head
       return newHead
  }复制代码

• 翻转从固定位置到固定位置的节点 （力扣92题）

  function reverseBetween (head, left, right) {
      let headpre = new ListNode(0, head), // 创建虚拟头节点
          p = headpre
      const cnt = right - left + 1 // 要翻转的位数
      while (--left) { // 找到要翻转的起始节点的前一位 （假设left为1，循环不进入，p为虚拟头节点）
          p = p.next
      }
      p.next = reverseN(p.next, cnt) // 上边的reverseN方法
      return headpre.next
  };复制代码

• k个一组，翻转链表 （力扣25题）

  function reverseKGroup (head, k) {
      function reverseN () {} // 同上
  
      function hasN (head, n) { // 判断是否够n个一组
          let p = head
          let cnt = n
          while (p && --n ) { // 查询长度
              p = p.next
          }
          if (!p) return head // 不够翻转，原封不动返回
          return reverseN(head, cnt)
      }
      let newHead = new ListNode(0, head),
          p = newHead,
          q = p.next // 如果发生翻转，q即为下一组翻转的头节点的前一个节点
      
      while (1) {
          p.next = hasN(q, k) // 虚拟头节点指向新的头节点
          if (p.next == q) { // 如果不够翻转的时候，结束循环
              break
          }
          p = q
          q = p.next 
      }
      // 简写
      /* while ((p.next = hasN(q, k)) != q) {
          p = q
          q = p.next
      } */
      return newHead.next
  }复制代码

2. 删除链表的倒数第 N 个节点（力扣19题）

• 思路：创建一个虚拟头节点，创建两个指针，第一个指针指向虚拟头节点，第二个指针指向头节点，第二个指针先走N步，然后两个指针一起开始走，当第二个指针走到null的时候，第一个指针即指向了要被删除的节点的前一个节点

  function removeNthFromEnd (head, n) {
      if (!head) return null
      let newHead = new ListNode(0, head)
      let p = newHead, q = head
      while (n--) q = q.next
      while (q) {
          q = q.next
          p = p.next
      }
      p.next = p.next.next
      return newHead.next
  }复制代码

3. 删除排序链表中重复节点（力扣83题）

```
function deleteDuplicates (head) {
    let p = head

    while (p && p.next) {
      let next = p.next
      while (p.val === (next && next.val)) { // 循环找到所有重复节点
          p.next = p.next.next
          next = p.next
      }
      p = p.next
    }
    return head
}
```复制代码

4. 力扣82题

```
function deleteDuplicates (head) {
    let newHead = new ListNode(NaN, head) // 头节点如果会发生变化，创建虚拟头节点方便操作
    let pre = newHead
    let p = head
    while (p && p.next) {
        if (p.val === p.next.val) { // 如果发现重复节点
            let next = p.next
            while ((next && next.val) === p.val) { // 遍历找到下一个不重复的节点
                next = next.next
            }
            pre.next = next // 把重复节点全部跳过
        } else {
            pre = pre.next // 如果没有重复，则上一个节点右移一位
        }
        p = pre.next // 当前遍历的节点直接跳到下一个未重复的节点
    }
    return newHead.next
}
```复制代码

5. 环形链表（力扣141题）

• 思路：设定快慢指针，如果存在链表有环，则快指针必定会追上慢指针

  function hasCycle (head) {
      if (!head || !head.next) return false
      let slow = fast = head
      do {
          slow = slow.next // 慢指针一次右移一位
          fast = fast.next.next // 快指针一次右移两位
      } while (slow !== fast && fast && fast.next)
      return fast != null && fast.next != null
  }复制代码

5-1. 延伸（力扣142题）

• 思路：第一次相遇时的位置距离环的起点等于从头开始到环的起点位置

  function detectCycle (head) {
      if (!head || !head.next) return null
      let slow = fast = head
      do {
          slow = slow.next
          fast = fast.next.next
      } while (slow !== fast && fast && fast.next) // 到这里为止同上边一样
      
      if (fast && fast.next) { // 如果有环
          slow = head // 设置其中一个节点从头开始，并以相同的速度
          while (fast != slow) { // 当再次相等时
              fast = fast.next
              slow = slow.next
          }
          return fast
      }
      return null
  }复制代码

6. 旋转链表 （力扣61题）

• 思路：首先让链表首尾相接形成环形链表，然后继续右移length - k%length

  function rotateRight (head, k) {
      if (!head || !head.next) return head
      let last = head
      let length = 1
      while (last.next) {
          length++
          last = last.next
      }
      last.next = head // 首尾相接
      let num = length - k%length // 长度 - k
      while (num--) {
          last = last.next
      }
      let newHead = last.next // 暂存头节点
      last.next = null // 断开
      return newHead
  }复制代码

三. 链表扩展

1. js实现链表

```
class LinkList {
    constructor() {
        this._length = 0
        this._head = null
        this._tail = null
    }
    
    append () {}  // 添加一个节点
    get () {}     // 返回指定索引位置的节点
    head () {}    // 返回头节点
    tail () {}    //  返回尾节点
    length () {}  // 返回链表长度
    isEmpty () {} // 返回链表是否为空
    clear () {}   // 清空链表
    indexOf () {} // 返回指定节点的索引
    remove () {}  // 删除指定位置的节点
    insert () {}  // 在指定位置插入一个节点
}
```

作者：姚头
链接：https://juejin.cn/post/7025191838483120159