Java 中查找链表倒数第 K 个节点

2025年5月6日 | 阅读 5 分钟

这是 **Google、Amazon、TCS、Accenture、Flipkart** 等顶级 IT 公司面试中经常出现的问题。通过解决这个问题，可以考察面试者的逻辑思维能力、批判性思维和解决问题的能力。因此，在本节中，我们将使用不同的方法和逻辑来查找 **链表倒数第 K 个节点**。我们还将创建 Java 程序来实现这一点。

问题陈述

给定一个链表和一个整数 K，我们需要找到倒数第 K 个节点。如果 K 大于节点数，则返回 -1。让我们通过一个例子来理解。

示例-1

输入: 10 -> 25 -> 30 -> 45 -> 50, N = 2

输出 45

解释: 节点 45 是链表倒数第二个节点。

示例-2

输入: 5 -> 10 -> 15 -> 20 -> 25, N = 1

输出 25

解释: 节点 25 是链表的最后一个节点（倒数第 1 个节点）。

朴素方法

朴素方法首先通过遍历链表来计算其总长度。然后，它计算所需节点从开头开始的位置，并再次遍历链表以到达该节点。

算法

步骤 1: 遍历链表以计算其总长度。

步骤 2: 如果 N 大于长度，则返回 -1（无效位置）。

步骤 3: 计算从开头开始的位置为 (长度 - N + 1)。

步骤 4: 从头开始移动到计算出的目标位置。

步骤 5: 到达目标节点后，返回其值。

实施

文件名: NavieApproach.java

// Class representing a node in the linked list
class ListNode {
    // Variable to store the data value of the node
    int value;
    // Reference to the next node in the linked list
    ListNode next;

    // Constructor to initialize the node with a value and set next as null
    ListNode(int value) {
        this.value = value;
        next = null; // Initially, there is no next node, so set to null
    }
}
// Main class containing the logic to find the Nth node from the end
public class NavieApproach {
    // Static method to find the Nth node from the end of the linked list
    static int getNthFromEnd(ListNode headNode, int positionFromEnd) {
        // Variable to store the length of the linked list
        int length = 0;
        // Temporary pointer to traverse the linked list from the head
        ListNode currentNode = headNode;
        // Loop to calculate the total length of the linked list
        while (currentNode != null) {
            // Move to the next node in the list
            currentNode = currentNode.next;
            // Increment the length counter by 1
            length++;
        }
        // Check if the required position from end is greater than the length
        if (length < positionFromEnd)
            return -1; // Return -1 if the position is invalid
        // Reset the currentNode pointer to the head to start traversing again
        currentNode = headNode;
        // Loop to move the pointer to the (length - positionFromEnd + 1)th node
        for (int i = 1; i < length - positionFromEnd + 1; i++)
            currentNode = currentNode.next; // Move to the next node
        // Return the value of the Nth node from the end
        return currentNode.value;
    }
    // Main method to execute the program
    public static void main(String[] args) {
        // Create the head node with value 10
        ListNode headNode = new ListNode(10);
        // Link the second node with value 25 to the head node
        headNode.next = new ListNode(25);
        // Link the third node with value 30
        headNode.next.next = new ListNode(30);
        // Link the fourth node with value 45
        headNode.next.next.next = new ListNode(45);
        // Link the fifth node with value 50
        headNode.next.next.next.next = new ListNode(50);
        // Print the value of the 3rd node from the end
        System.out.println(getNthFromEnd(headNode, 3));
    }
}   

输出

使用双指针法

该代码使用两个指针来高效地查找链表倒数第 N 个节点。一个指针向前移动 N 步，然后两个指针一起移动，直到第一个指针到达链表末尾，此时第二个指针指向所需的节点。

算法

步骤 1: 初始化两个指针 firstPointer 和 secondPointer，都指向链表的头部。

步骤 2: 将 firstPointer 向前移动 N 步。如果在完成 N 步之前 firstPointer 到达链表末尾，则返回 -1，因为链表中节点少于 N 个。

步骤 3: 每次将两个指针都向前移动一步，直到 firstPointer 到达链表末尾。

步骤 4: 当 firstPointer 到达链表末尾时，secondPointer 将指向倒数第 N 个节点。

步骤 5: 访问并返回 secondPointer 指向的节点值，即倒数第 N 个节点。

实施

文件名: NthNodeFromEnd.java

// Class representing a node in the linked list
class ListNode {
    // Variable to store the data value of the node
    int value;
    // Reference to the next node in the linked list
    ListNode next;
    // Constructor to initialize the node with a value and set next as null
    ListNode(int value) {
        this.value = value;
        next = null; // Initially, there is no next node, so set to null
    }
}
// Main class containing the logic to find the Nth node from the end using two pointers
public class NthNodeFromEnd {
    // Static method to find the Nth node from the end of the linked list using two pointers
    static int getNthFromEnd(ListNode headNode, int positionFromEnd) {
        // Initialize two pointers, both starting at the head node
        ListNode firstPointer = headNode;
        ListNode secondPointer = headNode;
        // Move the first pointer `positionFromEnd` steps ahead
        for (int i = 0; i < positionFromEnd; i++) {
            // If the list has fewer nodes than `positionFromEnd`, return -1
            if (firstPointer == null) {
                return -1;
            }
            // Move the first pointer one step forward
            firstPointer = firstPointer.next;
        }
        // Move both pointers until the first pointer reaches the end of the list
        while (firstPointer != null) {
            firstPointer = firstPointer.next; // Move the first pointer one step
            secondPointer = secondPointer.next; // Move the second pointer one step
        }
        // The second pointer now points to the Nth node from the end
        return secondPointer.value;
    }
    // Main method to execute the program
    public static void main(String[] args) {
        // Create the head node with value 10
        ListNode headNode = new ListNode(10);
        // Link the second node with value 25 to the head node
        headNode.next = new ListNode(25);
        // Link the third node with value 30
        headNode.next.next = new ListNode(30);
        // Link the fourth node with value 45
        headNode.next.next.next = new ListNode(45);
        // Link the fifth node with value 50
        headNode.next.next.next.next = new ListNode(50);
        // Print the value of the 3rd node from the end
        System.out.println(getNthFromEnd(headNode, 3));
    }
}   

输出

时间复杂度: O(M)，其中 M 是链表中的节点数，因为链表被遍历了两次。

空间复杂度: O(1)，因为只使用了两个指针，只需要恒定的额外空间。

下一个主题Java 丑数

← 上一个下一个 →

Java 中查找链表倒数第 K 个节点

问题陈述

朴素方法

算法

实施

使用双指针法

算法

实施

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Java 中查找链表倒数第 K 个节点

问题陈述

朴素方法

算法

实施

使用双指针法

算法

实施

相关帖子

How to Improve Coding Skills in Java

Java 程序以矩阵形式表示线性方程

How to Print Table in Java Using Formatter

Java 17 有什么新功能

REPL in Java

Externalization in Java

Reader read(CharBuffer) Method in Java with Examples

Java 中的质数点

Java 中的三元运算符

Read CSV File in Java

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器