题目描述

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

注意：链表至少包含两个节点。

示例：

• 给定链表 1->2->3->4->5 和 N = 2，删除倒数第二个节点后，链表变为 1->2->3->5。
• 给定链表 1 和 N = 1，删除链表中唯一的节点，返回 null。

PHP 示例代码

<?php

class ListNode {
    public $val;
    public $next;
    
    function __construct($val = 0, $next = null) {
        $this->val = $val;
        $this->next = $next;
    }
}

function removeNthFromEnd($head, $n) {
    // 使用双指针法
    $dummy = new ListNode(0, $head); // 创建一个哑节点，便于处理删除头节点的情况
    $fast = $dummy;
    $slow = $dummy;
    
    // 快指针先走 n+1 步
    for ($i = 0; $i <= $n; $i++) {
        $fast = $fast->next;
    }
    
    // 快慢指针同步移动，直到快指针到达链表末尾
    while ($fast !== null) {
        $fast = $fast->next;
        $slow = $slow->next;
    }
    
    // 删除倒数第 N 个节点
    $slow->next = $slow->next->next;
    
    return $dummy->next; // 返回哑节点的下一个节点，即原链表的头节点（或新头节点）
}

// 示例用法
$head = new ListNode(1);
$head->next = new ListNode(2);
$head->next->next = new ListNode(3);
$head->next->next->next = new ListNode(4);
$head->next->next->next->next = new ListNode(5);

$n = 2;
$result = removeNthFromEnd($head, $n);

// 打印结果链表（这里仅示意，实际PHP环境需自行实现打印函数）
// printList($result);

?>

Python 示例代码

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

def removeNthFromEnd(head, n):
    dummy = ListNode(0, head)  # 创建哑节点
    fast = slow = dummy
    
    # 快指针先走 n+1 步
    for _ in range(n + 1):
        fast = fast.next
    
    # 快慢指针同步移动
    while fast:
        fast = fast.next
        slow = slow.next
    
    # 删除倒数第 N 个节点
    slow.next = slow.next.next
    
    return dummy.next

# 示例用法
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
n = 2
result = removeNthFromEnd(head, n)

# 打印结果链表（这里仅为示意，Python环境可直接打印）
while result:
    print(result.val, end=" -> ")
    result = result.next
print("None")

JavaScript 示例代码

class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

function removeNthFromEnd(head, n) {
    let dummy = new ListNode(0, head); // 创建哑节点
    let fast = dummy;
    let slow = dummy;
    
    // 快指针先走 n+1 步
    for (let i = 0; i <= n; i++) {
        fast = fast.next;
    }
    
    // 快慢指针同步移动
    while (fast !== null) {
        fast = fast.next;
        slow = slow.next;
    }
    
    // 删除倒数第 N 个节点
    slow.next = slow.next.next;
    
    return dummy.next; // 返回哑节点的下一个节点，即原链表的头节点（或新头节点）
}

// 示例用法
let head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
let n = 2;
let result = removeNthFromEnd(head, n);

// 打印结果链表（这里仅为示意，JavaScript环境可直接通过遍历链表打印）
while (result) {
    console.log(result.val);
    result = result.next;
}

以上代码示例展示了如何在 PHP、Python 和 JavaScript 中删除链表的倒数第 N 个节点。这些示例都使用了双指针技术，其中一个指针先走 N+1 步，然后两个指针同时移动，直到快指针到达链表末尾，此时慢指针就指向了需要删除的节点的前一个节点。