删除链表的倒数第 N 个节点

题目要求
解题思路
Golang 版本
C++版本
Python 版本
Java 版本
Rust 版本
总结

题目要求

你需要编写一个算法来删除一个给定链表的倒数第 n 个节点，并返回修改后链表的头节点。

解题思路

要删除链表的倒数第 n 个节点，我们可以采用双指针法来解决这个问题。具体步骤如下：

初始化两个指针fast和slow都指向链表的头节点。
移动fast指针，使其与slow指针之间相隔 n 个节点。
同时移动fast和slow指针，直到fast指针指向链表的最后一个节点。
此时，slow指针将指向要删除节点的前一个节点。修改slow指针的next指向，让它跳过下一个节点，即完成了删除操作。
如果要删除的是头节点（即fast指针在步骤 2 中已经指向链表末尾），则直接返回头节点的下一个节点作为新的头节点。
返回修改后的链表的头节点。

注意：在实际操作中，我们需要考虑链表长度小于 n 的情况，以及 n 为 0 或负数的非法输入。对于这些情况，应当有相应的错误处理机制。

Golang 版本

type ListNode struct {
    Val int
    Next *ListNode
}

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    dummy := &ListNode{0, head} // 创建一个哑节点，指向头节点
    first := head
    second := dummy // second将从哑节点开始

    // 移动first，使得first和second之间相隔n个节点
    for i := 0; i < n; i++ {
        first = first.Next
    }

    // 移动first到末尾，同时移动second
    for first != nil {
        first = first.Next
        second = second.Next
    }

    // 此时second的下一个节点就是我们要删除的节点
    // 删除second的下一个节点
    second.Next = second.Next.Next

    // 返回哑节点的下一个节点，即新的头节点
    return dummy.Next
}

这段代码定义了一个链表节点的结构体ListNode，并实现了一个removeNthFromEnd函数，该函数接收链表的头节点head和一个整数n，返回删除链表倒数第n个节点后的头节点。代码中使用了一个哑节点来简化边界条件的处理，特别是当需要删除的节点是头节点时。

C++版本

#include <iostream>

// 定义链表节点结构体
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *dummy = new ListNode(0); // 创建一个哑节点
        dummy->next = head;
        ListNode *first = head;
        ListNode *second = dummy; // second从哑节点开始

        // 移动first指针，使其与second之间相隔n个节点
        for (int i = 0; i < n; ++i) {
            first = first->next;
        }

        // 同时移动first和second指针，直到first指向链表末尾
        while (first != nullptr) {
            first = first->next;
            second = second->next;
        }

        // 此时second的下一个节点就是我们要删除的节点
        ListNode *toDelete = second->next;
        second->next = second->next->next;

        delete toDelete; // 释放被删除节点的内存

        ListNode *newHead = dummy->next;
        delete dummy; // 删除哑节点
        return newHead; // 返回新的头节点
    }
};

这段 C++代码定义了一个链表节点的结构体ListNode和一个解决问题的类Solution。Solution类中的removeNthFromEnd成员函数实现了删除链表倒数第n个节点的功能，并返回新的头节点。代码中使用了一个哑节点来处理边界情况，特别是当需要删除的节点是头节点时。在删除节点后，代码还负责释放被删除节点的内存。

Python 版本

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        dummy = ListNode(0)
        dummy.next = head
        fast = slow = dummy

        # Move fast ahead by n+1 steps to maintain the gap between fast and slow
        for _ in range(n + 1):
            fast = fast.next

        # Move both pointers until fast reaches the end
        while fast:
            fast = fast.next
            slow = slow.next

        # Slow is now at the node before the one we want to remove
        slow.next = slow.next.next

        return dummy.next  # Return the head of the modified list

这段 Python 代码定义了一个链表节点类ListNode和一个解决问题的类Solution。Solution类中的removeNthFromEnd方法实现了删除链表倒数第n个节点的功能，并返回新的头节点。代码中使用了一个哑节点（dummy node）来简化边界条件的处理，特别是当需要删除的节点是头节点时。

Java 版本

public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode first = dummy;
        ListNode second = dummy;

        // Move first to the n+1 position
        for (int i = 1; i <= n + 1; i++) {
            first = first.next;
        }

        // Move first to the end, maintaining the gap
        while (first != null) {
            first = first.next;
            second = second.next;
        }

        // Skip the desired node
        second.next = second.next.next;

        return dummy.next;
    }
}

这段 Java 代码定义了一个链表节点类ListNode和一个解决问题的类Solution。Solution类中的removeNthFromEnd方法实现了删除链表倒数第n个节点的功能，并返回新的头节点。代码中使用了一个哑节点（dummy node）来简化边界条件的处理，特别是当需要删除的节点是头节点时。

Rust 版本

#![allow(unused)]
fn main() {
// Definition for singly-linked list.
#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
    pub val: i32,
    pub next: Option<Box<ListNode>>,
}

impl ListNode {
    #[inline]
    fn new(val: i32) -> Self {
        ListNode {
            next: None,
            val,
        }
    }
}

pub struct Solution;

impl Solution {
    pub fn remove_nth_from_end(head: Option<Box<ListNode>>, n: i32) -> Option<Box<ListNode>> {
        let mut dummy = Some(Box::new(ListNode { val: 0, next: head }));
        let mut fast = dummy.as_ref();
        let mut slow = &mut dummy;

        for _ in 0..n {
            if let Some(f) = fast {
                fast = f.next.as_ref();
            }
        }

        while let Some(f) = fast {
            fast = f.next.as_ref();
            slow = &mut slow.as_mut().unwrap().next;
        }

        let next = slow.as_mut().unwrap().next.take();
        slow.as_mut().unwrap().next = next.and_then(|node| node.next);

        dummy.unwrap().next
    }
}
}

这段 Rust 代码定义了一个单链表节点结构体ListNode和一个解决问题的结构体Solution。Solution结构体中的remove_nth_from_end函数实现了删除链表倒数第n个节点的功能，并返回新的头节点。代码中使用了Option<Box<ListNode>>来处理 Rust 中的所有权和可空性，以及一个哑节点（dummy node）来简化边界条件的处理，特别是当需要删除的节点是头节点时。

总结

上面给出的解法使用了双指针法来删除链表的倒数第 n 个节点。无论是使用的是哪种编程语言，解题思路都是一致的：通过维护两个指针之间的固定间隔，实现对链表的一次遍历即可找到要删除的节点。这种方法的时间复杂度为 O(N)，其中 N 是链表的长度，空间复杂度为 O(1)。在实际编码中，需要考虑链表长度小于 n 的情况，以及 n 为 0 或负数的非法输入，对这些情况应当有相应的错误处理机制。

hot-100