My Muri Life

切换主题

本页目录

环形链表篇 ​

判断是否成环 ​

141. 环形链表

双指针 ​

JavaScript
const hasCycle = head => {
  if (!head || !head.next) return false
  let [slow, fast] = [head.next, head.next.next]
  while (slow != fast) {
    if (!fast || !fast.next) return false
    slow = slow.next
    fast = fast.next.next
  }
  return true
}

时间复杂度：O(n)；空间复杂度：O(1)。

节点标记 ​

JavaScript
const hasCycle = head => {
  if (!head || !head.next) return false
  while (head.next) {
    if (head.tag) return true
    head.tag = true
    head = head.next
  }
  return false
}

时间复杂度：O(n)；空间复杂度：O(n)。

利用Set ​

JavaScript
const hasCycle = head => {
  const set = new Set()
  while (head) {
    if (set.has(head)) return true
    set.add(head)
    head = head.next
  }
  return false
}

时间复杂度：O(n)；空间复杂度：O(n)。

利用JSON.stringify ​

JavaScript
const hasCycle = head => {
  try {
    JSON.stringify(head)
  } catch {
    return true
  }
  return false
}

找出入环点 ​

142. 环形链表 II

双指针 ​

解题思路

初始化快fast慢slow指针，找出相遇点，然后将快指针重置为链表头， 再按相同速度步进直到再次相遇，此时的相遇点即入环点。

JavaScript
const detectCycle = head => {
  if (!head || !head.next) return null
  let [slow, fast] = [head.next, head.next.next]
  while (slow != fast) {  // 找出相遇点
    if (!fast || !fast.next) return null
    slow = slow.next
    fast = fast.next.next
  }
  fast = head  // 重置快指针为表头
  while (true) {
    if (slow == fast) break
    slow = slow.next
    fast = fast.next
  }
  return fast
}

时间复杂度：O(n)；空间复杂度：O(1)。

利用Set ​

JavaScript
const detectCycle = head => {
  const set = new Set()
  while (head) {
    if (set.has(head)) return head
    set.add(head)
    head = head.next
  }
  return null
}

时间复杂度：O(n)；空间复杂度：O(n)。

相交链表 ​

剑指 Offer II 023. 两个链表的第一个重合节点

双指针 ​

解题思路

定义双指针，分别指向链表A和链表B的头部：

  • 若链表一样长且有交点，则第一次遍历就能找到相同交点；
  • 若链表不一样长且有交点，则指针遍历一条链表后，遍历另一条链表， 两个指针在第二次遍历的时候，一定会在相交节点处相遇；
  • 若没有交点，则第二次遍历结束都是null，最终一定都会指向null。
JavaScript
const getIntersectionNode = (A, B) => {
  if (!A || !B) return null
  let [currA, currB] = [A, B]
  while (currA != currB) {
    currA = currA ? currA.next : B
    currB = currB ? currB.next : A
  }
  return currA
}

时间复杂度：O(m+n)；空间复杂度：O(1)。

旋转链表 ​

61. 旋转链表

成环 ​

解题思路

设链表长为len，考虑到k > len时，由于每len次移动都会让链表复原，故只需要移动k % len步即可：

  • 从head开始遍历链表，找到链表最后一个节点，并计算链表长度len；
  • 计算出旋转后链表的尾节点k = len - k % len；
  • 将链表连接成环，然后在环中迭代k步，此时的curr即为旋转后的链表尾节点；
  • 保存旋转后的链表头节点，并切断环。
  • 特别地，当链表长度不大于1，或者k为len的整数倍时，新链表将与原链表相同。

返回新链表。

JavaScript
const rotateRight = (head, k) => {
  if (!k || !head || !head.next) return head
  let [curr, len] = [head, 1]
  // 找到链表的最后一个节点
  while (curr.next) {
    len++
    curr = curr.next
  }
  // 移动后的尾节点
  k = len - k % len
  if (k === len) return head
  // 连接成环
  curr.next = head
  while (k--) {
    curr = curr.next
  }
  const newHead = curr.next
  // 切断环
  curr.next = null
  return newHead
}

时间复杂度：O(n)；空间复杂度：O(1)。