题目描述

给定一个单链表，要求找到该链表中倒数第n个节点。如果链表的长度小于n，则返回null（或在特定语言中为None/null/undefined等，表示不存在）。

示例

假设链表是 1 -> 2 -> 3 -> 4 -> 5，且 n = 2。

则倒数第n个节点是 4。

PHP 代码示例

<?php

class ListNode {
    public $val;
    public $next;

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

function findNthFromEnd($head, $n) {
    $slow = $head;
    $fast = $head;

    // 先让快指针向前走n步
    for ($i = 0; $i < $n; $i++) {
        if ($fast == null) {
            // 链表长度小于n
            return null;
        }
        $fast = $fast->next;
    }

    // 快慢指针同时移动，直到快指针到达末尾
    while ($fast != null) {
        $slow = $slow->next;
        $fast = $fast->next;
    }

    // 慢指针此时指向倒数第n个节点
    return $slow;
}

// 示例用法
$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 = findNthFromEnd($head, $n);
if ($result) {
    echo "倒数第{$n}个节点的值为: " . $result->val;
} else {
    echo "链表长度小于{$n}，不存在倒数第{$n}个节点";
}

?>

Python 代码示例

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

def findNthFromEnd(head: ListNode, n: int) -> ListNode:
    slow = fast = head
    for _ in range(n):
        if not fast:
            return None
        fast = fast.next
    while fast:
        slow = slow.next
        fast = fast.next
    return slow

# 示例用法
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)

n = 2
result = findNthFromEnd(head, n)
if result:
    print(f"倒数第{n}个节点的值为: {result.val}")
else:
    print(f"链表长度小于{n}，不存在倒数第{n}个节点")

JavaScript 代码示例

function ListNode(val, next) {
    this.val = (val===undefined ? 0 : val)
    this.next = (next===undefined ? null : next)
}

function findNthFromEnd(head, n) {
    let slow = head;
    let fast = head;

    // 先让快指针向前走n步
    for (let i = 0; i < n; i++) {
        if (!fast) return null;
        fast = fast.next;
    }

    // 快慢指针同时移动，直到快指针到达末尾
    while (fast) {
        slow = slow.next;
        fast = fast.next;
    }

    // 慢指针此时指向倒数第n个节点
    return slow;
}

// 示例用法
let 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);

let n = 2;
let result = findNthFromEnd(head, n);
if (result) {
    console.log(`倒数第${n}个节点的值为: ${result.val}`);
} else {
    console.log(`链表长度小于${n}，不存在倒数第${n}个节点`);
}

码小课网站中有更多相关内容分享给大家学习，包括链表操作的进阶技巧、其他数据结构的面试题解析等。