题目

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

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

解题

第一个反应是做一个切片，用来存储链表的所有节点，然后根据 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
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNthFromEnd(head *ListNode, n int) *ListNode {
	if head == nil || head.Next == nil {
		return nil
	}

	nodes := make([]*ListNode, 0)
	for node := head; node != nil; node = node.Next {
		nodes = append(nodes, node)
	}

	if idx := len(nodes) - n; idx == 0 { // remove the first node
		return head.Next
	} else if tail := len(nodes) - 1; tail == idx { // remove the last node
		nodes[idx-1].Next = nil
	} else {
		nodes[idx-1].Next = nodes[idx+1] // remove the middle node
	}

	return head
}

这种方法的时间复杂度是 O(n)，空间复杂度也是 O(n)，因为需要存储所有节点。

如果考虑降低空间复杂度，那就需要使用双指针的方法。因为要删除链表的倒数第 n 个节点，所以当前指针走到链表的末尾（nil），后指针应该正好在倒数第 n 个节点的前一个位置。也就是说两个指针中间需要正好间隔 n 个节点。

在编码上，考虑到可能会删除链表的头节点，所以习惯上做一个哑巴节点，最后代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNthFromEnd(head *ListNode, n int) *ListNode {
	dummy := &ListNode{Next: head}
	slow := dummy
	for fast := head; fast != nil; fast = fast.Next {
		if n > 0 {
			n--
		} else {
			slow = slow.Next
		}
	}
	slow.Next = slow.Next.Next

	return dummy.Next
}

这种方法的时间复杂度是 O(n)，空间复杂度是 O(1)，因为只使用了两个指针，没有额外的空间开销。

总结

这种题目需要注意链表的边界情况，比如链表为空、只有一个节点、删除头节点等。使用哑巴节点可以简化代码逻辑，避免处理头节点的特殊情况。

想到用栈/数组来存储节点是一个不错的思路，但如果考虑到空间复杂度，使用双指针的方法更为高效。双指针方法的关键在于理解如何通过两个指针的相对位置来定位需要删除的节点，这种技巧在处理链表问题时非常常见且实用。