LeetCode-剑指offer21.删除链表中倒数第n个节点

发表于 分类于

题目描述

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

示例

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

提示：

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

题解

  1. 给链表添加一个表头，处理删掉第一个元素时的情况。
  2. 准备一个快指针，在链表上先走n步。
  3. 准备慢指针指向原始链表头，代表当前元素，前序节点指向添加的表头，这样两个指针之间相距就是一直都是n。
  4. 快慢指针同步移动，当快指针到达链表尾部的时候，慢指针正好到了倒数n个元素的位置。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/** 链表节点 */
class ListNode {
  var val: Int
  var next: ListNode?
  init(_ val: Int) {
      self.val = val
      self.next = nil
  }
}

func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
  let newHead = ListNode(0)
  newHead.next = head
  var pre: ListNode? = newHead
  var cur = head
  var fast = head
  for _ in 0 ..< n {
    if fast !== nil {
      fast = fast?.next
    } else {
      return head
    }
  }
  while fast != nil {
    fast = fast?.next
    pre = cur
    cur = cur?.next
  }
  pre?.next = cur?.next
  return newHead.next
}