链表

移除链表元素

想要移除一个链表的节点,其实特别简单,只需要 p.next = p.next.next 即可。也就是说,要想删除某个节点,只要找到删除节点的前一个节点 p,然后让 p 的下一个节点指向删除节点的下一个节点即可。但是问题在于,如果移动的是头节点呢?头节点找不到前一个节点,所以我们其实只需要把头节点指向下一个节点就行了。但是这样删除方法其实并没有统一,这就是 dummyHead 虚拟头节点引入的意义 —— 统一头节点和非头节点的处理方法。

另外,这里 while 循环的条件为什么是 p.next,而不是 p 呢?因为假设我们要删除某个节点,就需要找到它的前一个节点,但是对于单向链表来说,前一个节点是获取不到的,所以我们只能换一种思考方式:从前一个节点 p 开始遍历,然后需要删除的时候删除掉 p.next 这个节点。

function removeElements(head: ListNode | null, val: number): ListNode | null {
  const dummyHead = new ListNode(-1, head)
  // 这里 p 指向的是被删元素的上一个元素
  let p = dummyHead
  while (p.next) {
    if (p.next.val === val) {
      p.next = p.next.next
    } else {
      p = p.next
    }
  }

  return dummyHead.next
}

设计链表

这是一道非常非常复杂的模拟题,甚至比 LRU 还要复杂得多,复杂主要体现在太容易出错了,我也因为一些细节问题 debug 了挺长时间。题目要求我们可以在单链表和双链表之间做选择,很显然这里选择双链表会更合适,可以保证时间复杂度更小。因为对于尾部的插入我们可以直接利用虚拟尾节点实现 O(1) 插入;对于中间部分的节点插入,我们也可以计算出该节点的遍历方向,靠左就从左向右遍历,靠右就从右向左遍历,保证了最小遍历次数。但是对于节点的插入,依然是很容易出错的,这里建议是使用画图的方法,确保不要写漏其中的某个关系。以 addAtIndex 函数为例:

addAtIndex

class LinkedNode {
  public prev: null | LinkedNode = null
  public next: null | LinkedNode = null
  public val: number

  constructor(val: number) {
    this.val = val
  }
}

class MyLinkedList {
  private dummyHead = new LinkedNode(-1)
  private dummyTail = new LinkedNode(-1)
  private length = 0

  constructor() {
    this.dummyHead.next = this.dummyTail
    this.dummyTail.prev = this.dummyHead
  }

  get(index: number) {
    if (index >= this.length || index < 0) {
      return -1
    }

    return this.getNode(index).val
  }

  addAtHead(val: number) {
    const newHead = new LinkedNode(val)
    newHead.next = this.dummyHead.next
    newHead.prev = this.dummyHead
    newHead.next.prev = newHead
    this.dummyHead.next = newHead
    this.length++
  }

  addAtTail(val: number) {
    const newTail = new LinkedNode(val)
    newTail.prev = this.dummyTail.prev
    newTail.next = this.dummyTail
    newTail.prev.next = newTail
    this.dummyTail.prev = newTail
    this.length++
  }

  addAtIndex(index: number, val: number) {
    if (index > this.length) {
      return
    }
    if (index < 0) {
      this.addAtHead(val)
      return
    }
    if (index === this.length) {
      this.addAtTail(val)
      return
    }
    const p = this.getNode(index)
    const newNode = new LinkedNode(val)
    newNode.next = p
    newNode.prev = p.prev
    p.prev.next = newNode
    p.prev = newNode
    this.length++
  }

  deleteAtIndex(index: number) {
    if (index >= 0 && index < this.length) {
      const p = this.getNode(index)
      p.prev.next = p.next
      p.next.prev = p.prev
      this.length--
    }
  }

  /** 注意该函数不包括边界判断 */
  private getNode(index: number) {
    const findFromLeft = index < Math.floor(this.length / 2)
    if (!findFromLeft) {
      index = this.length - 1 - index
    }
    let p = findFromLeft ? this.dummyHead.next : this.dummyTail.prev
    for (let i = 0; i < index; i++) {
      p = findFromLeft ? p.next : p.prev
    }
    return p
  }
}

反转链表

反转链表有双指针和递归两种写法,都需要掌握。双指针的解法比较容易理解,但是递归的方法会让人比较懵。我们可以选择从双指针解法推导出递归的解法。具体怎么推导有点玄学,文字很难说明清楚,可以看代码随想录的视频讲解

// 双指针
function reverseList(head: ListNode | null): ListNode | null {
  let prev = null, cur = head
  // 边界条件,当 cur 为 null 时,pre(cur 的前一个节点)刚好指向链表尾部,也就是反转之后的头节点
  while (cur) {
    // 存储 cur 的下一个节点,否则链表无法继续遍历下去
    const temp = cur.next
    cur.next = prev
    prev = cur
    cur = temp
  }
  return prev
}
// 递归
function reverseList(head: ListNode | null): ListNode | null {
  return helper(null, head)
  
  function helper(prev: ListNode | null, cur: ListNode | null) {
    if (!cur) {
      return prev
    }
    const temp = cur.next
    cur.next = prev
    return helper(cur, temp)
  }
}

两两交换链表中的节点

图示

这道题目也算是有一定难度的题目,对于边界的处理和链表基本操作的要求都比较高。

先思考一下边界条件,这道题要两两交换链表的节点,比如说要交换 2 和 3 节点,就需要在 2 前面的节点 1(假设叫 p)执行类似 p.next.next = 节点 2 的操作,那么对于头节点我们就要额外判断处理。所以这里为了统一操作,我们可以选择使用 dummyHead,如下所示。

dummyHead

然后思考边界条件,分为奇偶处理。如果现在有奇数个节点,比如图中有 5 个节点,我们的 current 指针会依次指向 dummyHead,进行节点 1 和节点 2 的交换;然后指向节点 2,进行节点 3 和 节点 4 的交换;然后指向节点 4,此时节点 5 已经是尽头,不需要再进行交换。所以当有奇数个节点时边界为 current.next.next !== null。然后我们再设想一下,对于偶数个节点,例如现在如果没有节点 5,那么 4 相当于直接指向了 null,此时的边界条件很显然是 current.next !== null。综上可得边界条件是 current.next !== null && current.next.next !== null

现在开始进行交换。让 dummyHead 的指针指向 2,然后 2 的指针再指向 1,然后 1 的指针再指向 3。

交换节点

这里就涉及到如果获取节点 1 了,我们执行完 current.next = current.next.next 之后,其实 current.next 就已经不再是节点 1 了,所以我们需要先用一个临时变量存储一下节点 1。同样的道理,我们节点 2 指向节点 1 之后,就拿不到节点 3 了,那 1 就没办法指向节点 3 了,所以我们还需要一个临时变量来存储一下节点 3 的值。明白这些之后我们就可以实现这道题的代码了。实现起来还是比较复杂的,但是只要结合画图解决问题,就会难度小很多。

function swapPairs(head: ListNode | null): ListNode | null {
  const dummyHead = new ListNode(-1, head)
  let p = dummyHead
  while (p.next && p.next.next) {
    const temp = p.next // 节点 1
    const temp1 = p.next.next.next // 节点 3
    p.next = p.next.next // dummy 指向节点 2
    p.next.next = temp // 节点 2 指向节点 1
    temp.next = temp1 // 节点 1 指向节点 3
    p = p.next.next // 移动 dummy(此时节点 1 和节点 2 位置已经变换,但是并不影响我们继续遍历)
  }
  return dummyHead.next
}

删除链表的倒数第 N 个结点

图示

这道题其实是一个经典的快慢指针问题。首先思考一下,要删除一个节点该怎么做,很显然,我们需要获得这个节点的前一个节点。现在假设 n = 3。令快指针 fast 和慢指针 slow 都指向 dummyHead,然后我们让指针 fast 先走 n 步,fast 就会来到指针 3 的位置。然后我们再同时移动 fast 和 slow 直到 fast 移动到 null。显然此时 fast 指向 null,而 slow 指向 2。我们要删除倒数第 3 个节点 2,就要让 slow 指向 1,而 现在 slow 指向了 2,多指了一位,所以 fast 要移动多一步,也就是我们开始的时候需要先让 fast 移动 n + 1 步。

function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
  const dummyHead = new ListNode(-1, head)
  let fast = dummyHead, slow = dummyHead
  for (let i = 0; i < n + 1; i++) {
    fast = fast.next
  }
  while (fast) {
    fast = fast.next
    slow = slow.next
  }
  slow.next = slow.next.next

  return dummyHead.next
}

链表相交

我们先明确一下自己需要解决的问题。假设目前 curA 指向链表 A 的头结点,curB 指向链表 B 的头结点,如果 curA 和 curB 分别直接在两条链表上移动,并不能同时走到公共节点,也就无法得到相交节点了。所以我们要解决的问题就是通过某些方式,使得 curA 和 curB 能够同时到达相交节点。而且我们很容易知道,如果节点 A 和节点 B 相交于点 P,则 P 后面的部分都是两链表的重叠部分。因此,只要让两个链表的尾部对齐,就可以进行对比了。

图示

我们先求出两个链表的长度,并求出两个链表长度的差值,然后让 curA 移动,直到两个链表尾部对齐,而且可以同步移动节点,如图:

图示

此时我们就可以比较 curA 和 curB 是否相同,如果不相同,同时向后移动 curA 和 curB,如果遇到 curA === curB,则找到交点。

function getIntersectionNode(headA: ListNode | null, headB: ListNode | null): ListNode | null {
  let curA = headA, curB = headB
  let lenA = 0, lenB = 0
  while (curA) {
    lenA++
    curA = curA.next
  }
  while (curB) {
    lenB++
    curB = curB.next
  }

  curA = headA
  curB = headB

  if (lenA < lenB) {
    [lenA, lenB, curA, curB] = [lenB, lenA, curB, curA]
  }

  let gap = lenA - lenB
  // 补齐两个链表长度之差
  while (gap--) {
    curA = curA.next
  }

  while (curA) {
    if (curA === curB) {
      return curA
    }
    curA = curA.next
    curB = curB.next
  }

  return null
}

环形链表II

这道题定义快慢指针,快指针一次走 2 个节点,慢指针一次走一个节点。那么为什么要这么定义呢?假设现在快慢指针都已经进入到了环内,那么快指针相对于慢指针的移动速度是一次一个节点,所以快指针是一个节点一个节点地靠近慢指针,也就是必定会在环内相遇;反之如果快慢指针最终没有相遇,则说明链表无环。此时已经可以判断链表是否有环了,那么接下来要找这个环的入口了。

图示

相遇时:slow 指针走过的节点数为: x + y, fast 指针走过的节点数:x + y + n (y + z),n 为 fast 指针在环内走了 n 圈才遇到 slow 指针,(y+z) 为一圈内节点的个数。

因为 fast 指针一步走两个节点,slow 指针一步走一个节点, 所以 fast 指针走过的节点数 = slow 指针走过的节点数 * 2,也就是

(x + y) * 2 = x + y + n (y + z)

两边消掉一个(x+y)后得到:

x + y = n (y + z)

因为要找环形的入口,也就是说要求的是 x。将 x 单独放在左边:

x = n (y + z) - y

再从 n (y+z) 中提出一个 (y+z) 来,整理公式之后为如下公式:

x = (n - 1) (y + z) + z

注意这里 n 一定是大于等于 1 的,因为 fast 指针至少要多走一圈才能相遇 slow 指针。当 n 为 1 的时候,公式就化为:

x = z

这就意味着,从头结点 index1 出发一个指针,从相遇节点 index2 也出发一个指针,这两个指针每次只走一个节点,那么当这两个指针相遇的时候就是环形入口的节点。那么 n 如果大于 1 是什么情况呢,就是 fast 指针在环形转 n 圈之后才遇到 slow 指针。其实这种情况和 n 为 1 的时候效果是一样的,一样可以通过这个方法找到环形的入口节点,只不过,index2 指针在环里多转了 (n - 1) 圈,然后再遇到 index1,相遇点其实依然是环形的入口节点。

知道原理之后,其实这道题的代码实现倒是几乎没什么难度。

function detectCycle(head: ListNode | null): ListNode | null {
  let fast = head, slow = head

  while (fast && fast.next) {
    fast = fast.next.next
    slow = slow.next

    if (slow === fast) {
      let index1 = head, index2 = slow
      while (index1 !== index2) {
        index1 = index1.next
        index2 = index2.next
      }
      return index1
    }
  } 

  return null
}
©2022 Flower-F. All Rights Reserved.