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

一、问题描述

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

示例:

给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个结点后，链表变为 1->2->3->5.

说明:

• 给定的 n 保证是有效的。

二、方案一：双指针法

1、思路

使用两个指针，第一个指针从链表的头结点开始向前走 n 步，第二个指针保持不动。然后，同时移动两个指针，直到第一个指针到达链表的末尾。此时，第二个指针所指向的结点就是倒数第 n 个结点。

2、代码实现

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNthFromEnd(head *ListNode, n int) *ListNode {
	// 创建一个哑节点 dummy，将其 Next 指向链表的头部
	dummy := &ListNode{Next: head}
	// 使用两个指针 slow 和 fast，初始时它们都指向 dummy
	slow, fast := dummy, dummy
	// 将 fast 向前移动 n 个节点。
	for i := 0; i < n; i++ {
		fast = fast.Next
	}
	// 同时移动 slow 和 fast，直到 fast 到达链表的末尾。这时，slow 将指向倒数第 n 个节点
	pre := &ListNode{}
	for fast != nil {
		pre = slow
		slow = slow.Next
		fast = fast.Next
	}

	// 删除 slow 指向的节点，即倒数第 n 个节点
	pre.Next = slow.Next

	return dummy.Next
}

3、复杂度分析

• 时间复杂度：O(L)，其中 L 是链表的长度。
• 空间复杂度：O(1)，只使用了常数的额外空间。

三、方案二：计算长度法

1、思路

首先遍历整个链表，计算出链表的长度 L。然后再次从头开始遍历，当遍历到第 L - n 个结点时，其下一个结点即为要删除的结点。

2、代码实现

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    dummy := &ListNode{0, head} // 创建哑结点
    length := 0
    first := head
    // 计算链表长度
    for ; first != nil; first = first.Next {
        length++
    }
    // 移动到要删除的结点的前一个结点
    first = dummy
    for i := 0; i < length - n; i++ {
        first = first.Next
    }
    // 删除结点
    first.Next = first.Next.Next
    return dummy.Next
}

3、复杂度分析

• 时间复杂度：O(L)，其中 L 是链表的长度。
• 空间复杂度：O(1)，只使用了常数的额外空间。

是的，可以使用递归法来解决这个问题。递归法的基本思想是，递归遍历链表，到达链表尾部时开始计数，这样就可以在回溯过程中删除倒数第 n 个结点。

三、方案三：递归法

1、思路

递归遍历链表，当到达链表尾部时开始计数。在回溯过程中，每返回一层递归，计数器加一。当计数器等于 n 时，说明当前结点是倒数第 n 个结点的前一个结点，此时进行删除操作。

2、代码实现

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNthFromEnd(head *ListNode, n int) *ListNode {
	// 创建一个哑节点 dummy，将其 Next 指向链表的头部
	dummy := &ListNode{Next: head}
	remove(dummy, n)
	return dummy.Next
}

func remove(node *ListNode, n int) int {
	if node == nil {
		return 0
	}

	count := remove(node.Next, n) + 1
	if count == n+1 {
		node.Next = node.Next.Next
	}

	return count
}

3、复杂度分析

• 时间复杂度：O(L)，其中 L 是链表的长度。递归遍历了链表一次。
• 空间复杂度：O(L)，递归调用栈的深度可能会达到链表的长度。

四、总结

方案	时间复杂度	空间复杂度	备注
双指针法	O(L)	O(1)	只遍历链表一次
计算长度法	O(L)	O(1)	需要遍历链表两次
递归法	O(L)	O(L)	递归遍历链表
递归法在空间复杂度上不如前两种方法，因为它需要额外的空间来维护递归栈。在实际应用中，如果对空间复杂度有要求，通常更倾向于使用双指针法。