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

发表于 分类于 Disqus：

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：

img

1
2
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：

1
2
输入：head = [1], n = 1
输出：[]

示例 3：

1
2
输入：head = [1,2], n = 1
输出：[1]

提示：

  • 链表中结点的数目为 sz
  • 1 <= sz <= 30
  • 0 <= Node.val <= 100
  • 1 <= n <= sz

进阶：你能尝试使用一趟扫描实现吗？

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
  if head == nil { return head }
  
  var first: ListNode? = head
  var last: ListNode? = head
  var m = 0
  while first?.next != nil {
    first = first?.next
    if m == n {
      last = last?.next
    } else {
      m += 1
    }
  }
  
  if m < n {
    return head?.next
  }
  
  last?.next = last?.next?.next
  
  return head
}

算法使用了“双指针”技术，通过设置一个“快指针”和一个“慢指针”来高效地完成这个任务。

1. 空链表检查

1
if head == nil { return head }

与上一个版本一样，首先我们检查链表是否为空。如果链表为空，直接返回原链表。

2. 初始化两个指针

1
2
3
var first: ListNode? = head
var last: ListNode? = head
var m = 0

  • first 是快指针，最初指向链表的头节点。

  • last 是慢指针，最初也指向链表的头节点。

  • m 是一个计数器，帮助我们控制 last 指针移动的步数。

3. 移动快指针

1
2
3
4
5
6
7
8
while first?.next != nil {
  first = first?.next
  if m == n {
    last = last?.next
  } else {
    m += 1
  }
}

  • 这里我们开始循环，直到 first 指针走到链表的最后一个节点。

  • 在每次循环中，first 指针都会向前移动一步。

  • m 变量用于控制 last 指针的移动。如果 m 达到 n，意味着 first 指针已经走过了 n 步，此时我们开始让 last 指针也移动，这样 last 和 first 之间的距离就始终保持为 n。

4. 删除倒数第 N 个节点的特殊情况

1
2
3
if m < n {
  return head?.next
}

这一部分是处理特殊情况。如果链表的长度小于 n（例如 n 比链表长度还大），我们直接返回 head?.next，相当于删除头节点。

5. 删除倒数第 N 个节点

1
last?.next = last?.next?.next

一旦 first 指针到达链表的最后一个节点时，last 指针就会指向倒数第 n+1 个节点。此时，last?.next 就是倒数第 N 个节点。我们通过将 last?.next 指向 last?.next?.next，成功删除了倒数第 N 个节点。

6. 返回修改后的链表头

1
return head

最后，我们返回链表的头节点。即使删除了倒数第 N 个节点，链表的头节点仍然是原始头节点。

总结：

这段代码的关键思想与前一种解法类似：通过快慢指针的技巧来找出倒数第 N 个节点。主要不同点在于：

  • 该实现使用了 m 作为计数器来控制 last 指针的移动，直到 first 指针走了 n 步，last 指针才开始移动。

  • 处理链表长度小于 n 的情况时，通过返回 head?.next 来直接删除链表的头节点。

这种方式具有 O(L) 的时间复杂度和 O(1) 的空间复杂度，其中 L 是链表的长度。

优化后

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
  if head == nil { return nil }
  
  var fast: ListNode? = head
  for _ in 0..<n {
    guard let node = fast?.next else { return head?.next }
    fast = fast?.next
  }
  
  var low: ListNode? = head
  while let node = fast?.next {
    fast = node
    low = low?.next
  }
  
  low?.next = low?.next?.next
  
  return head
}

与上一种解法相比，这种写法实现方式有所不同，依然采用了类似的“双指针”技巧，但在处理快慢指针时的细节和逻辑略有不同。让我们逐步讲解这个算法的每一部分：

1. 初始化和空链表检查:

1
if head == nil { return nil }

首先，我们检查链表是否为空。如果是空链表，直接返回 nil。

2. 设置快指针:

1
2
3
4
5
var fast: ListNode? = head
for _ in 0..<n {
    guard let node = fast?.next else { return head?.next }
    fast = fast?.next
}

我们定义了一个 fast 指针，并将其初始化为链表的头节点。接下来，我们让 fast 指针先走 n 步。这样，fast 指针在执行完这个循环后，会离链表的尾部有 n 个节点的距离。

需要特别注意的是，如果链表长度小于 n，我们直接返回 head?.next，这是因为倒数第 N 个节点不存在，我们只需要删除链表中的第一个节点。

3. 设置慢指针:

1
2
3
4
5
var low: ListNode? = head
while let node = fast?.next {
    fast = node
    low = low?.next
}

现在，fast 指针已经向前走了 n 步，因此接下来，我们定义一个 low 指针，初始时指向头节点。然后，我们同时让 fast 和 low 一起向前移动，直到 fast 指针到达链表的最后一个节点。由于 fast 和 low 之间的距离保持为 n，当 fast 到达链表的尾部时，low 就会指向倒数第 n+1 个节点。

4. 删除倒数第 N 个节点:

1
low?.next = low?.next?.next

此时，low 指针指向的是倒数第 n+1 个节点，而 low?.next 就是我们要删除的倒数第 N 个节点。我们通过将 low?.next 的指针指向 low?.next?.next 来删除这个节点。

5. 返回结果:

1
return head

最后，我们返回修改后的链表头节点 head，这样链表中的节点已经删除了倒数第 N 个节点。

总结：

这个算法的关键点在于利用快慢指针的技巧。通过先让快指针走 n 步，然后快慢指针一起前进，直到快指针到达链表末尾，这样慢指针就能精确地定位到倒数第 n+1 个节点的位置。然后通过调整指针来删除倒数第 N 个节点，完成删除操作。这个算法的时间复杂度是 O(L)，其中 L 是链表的长度，空间复杂度是 O(1)，因为我们只使用了常数空间。