删除链表末尾的第 N 个

在这篇文章中，我探索了另一种链表算法。这个有点难。

创建一个函数来删除链表末尾的第 n 个节点。

这来自leetcode问题。与 leetcode 问题一样，“n”是从 1 开始的，可以从 1 到列表的长度。

func (ll *LinkedList[T]) RemoveNthFromEnd(n int) *Node[T] {
    if n == 0 {
        return nil
    }
    fast := ll.Head // this moves to the end
    slow := ll.Head // this should be one behind the nth from end

    for count := 0; count < n; count++ {
        if fast == nil { // list is too short
            return nil
        }
        fast = fast.Next
    }
    if fast == nil { // special case, removing head
        res := ll.Head
        ll.Head = ll.Head.Next
        return res
    }
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next
    }
    res := slow.Next
    slow.Next = slow.Next.Next
    return res
}

关键是使用双指针。我们首先初始化一个指向列表头部的快指针和慢指针。

接下来，我们将快指针向前移动 n 个节点。这样，慢指针现在位于快指针后面的“n”处。现在，我们可以以锁步方式移动两个指针，直到 fast 结束。

然后我们可以删除倒数第 n 个节点并将其返回。

有更好的方法吗？请在评论中告诉我。

谢谢！

这篇文章以及本系列所有文章的代码可以在这里找到

以上是删除链表末尾的第 N 个的详细内容。更多信息请关注PHP中文网其他相关文章！