Java 程序：从链表末尾查找第n个节点

Java 程序：从链表末尾查找第`n`个节点

原文：https://www.studytonight.com/java-programs/java-program-to-find-nth-node-from-end-of-linked-list

在本教程中，我们将看到如何在 java 中从链表的末尾找到第 n 个节点。LinkedList 是一种线性数据结构，其中元素不存储在连续的位置，每个元素都是一个单独的对象，具有数据部分和地址部分。每个元素都被称为一个节点。由于插入和删除的动态性和容易性，它们比数组更受欢迎。但是在继续之前，如果你不熟悉 java 中链表的概念，那么一定要查看一下 Java 中链表上的文章。

输入:输入链表元素:6 7 8 4 5 1 3 2 5

输出:链表末尾的第 6 个节点是:4

这可以通过使用以下方法来实现:

方法 1:使用链表的长度。

方法 2:使用两点概念。

让我们看看这些方法中的每一种，以便更好地理解。

Java 程序：程序 1:从链表末尾找到第 n 个节点

在这个程序中，我们将看到如何使用链表的长度在 java 中从链表的末尾找到第 n 个节点。

算法:

开始
使用链表数据结构创建String类型的链表。
现在向链表添加节点。
调用用户定义的函数，从链表的末尾开始计算第 n 个节点。
首先，计算链表的长度。
现在，打印链表开头的第(length–n+1)个节点。
停止

让我们看看下面的例子，以更好地理解上述算法。

//Java program to find nth node from end of linked list
public class LinkedList 
{
    Node head; 
    class Node 
    {
        int data;
        Node next;
        Node(int d)
        {
            data = d;
            next = null;
        }
    }
    void printNthFromEnd(int n)
    {
        int len = 0;
        Node temp = head;
        while (temp != null) 
        {
            temp = temp.next;
            len++;
        }
        if (len < n)
            return;
        temp = head;
        for (int i = 1; i < len - n + 1; i++)
            temp = temp.next;
        System.out.println(n+"th node from the end is "+temp.data);
    }
    public void add(int newData)
    {
        Node newNode = new Node(newData);
        newNode.next = head;
        head = newNode;
    }
    public static void main(String[] args)
    {
        LinkedList ll = new LinkedList();
        ll.add(12);
        ll.add(8);
        ll.add(21);
        ll.add(96);
        ll.add(52);
        ll.add(27);
        ll.add(14);
        ll.printNthFromEnd(6);
    }
}

距终点第 6 个节点是 27

Java 程序：程序 2:从链表末尾找到第 n 个节点

在这个程序中，我们将看到如何使用两个指针在 java 中从链表的末尾找到第 n 个节点。

算法:

开始
使用链表数据结构创建String类型的链表。
现在向链表添加节点。
调用用户定义的函数，从链表的末尾开始计算第 n 个节点。
声明两个指针:指针 1 和指针 2。
初始化指向 head 的两个指针。
首先，将第一个指针从头部移动到 n 个节点。
现在逐个移动两个指针，直到引用指针到达末尾。
现在第二个指针将从末尾指向第 n 个节点。
返回第二个指针。
显示结果。
停止

让我们看看下面的例子，以更好地理解上述算法。

//Java program to find nth node from end of linked list
public class LinkedList 
{
    Node head; 
    class Node 
    {
        int data;
        Node next;
        Node(int d)
        {
            data = d;
            next = null;
        }
    }
    void printNthFromEnd(int n)
    {
        Node ptr1 = head;
        Node ptr2 = head;

        int count = 0;
        if (head != null)
        {
            while (count < n)
            {
                if (ptr2 == null)
                {
                    System.out.println(n+ " is greater than the number of nodes in the list");
                    return;
                }
                ptr2 = ptr2.next;
                count++;
            }

            if(ptr2 == null)
            {
              head = head.next;
              if(head != null)
                System.out.println(n +"th node from the last is "+head.data);
            }
            else
            {

              while (ptr2 != null)
              {
                  ptr1 = ptr1.next;
                  ptr2 = ptr2.next;
              }
              System.out.println(n +"th node from the last is "+ptr1.data);
            }
        }

    }
    public void add(int newData)
    {
        Node newNode = new Node(newData);
        newNode.next = head;
        head = newNode;
    }
    public static void main(String[] args)
    {
        LinkedList ll = new LinkedList();
        ll.add(12);
        ll.add(8);
         ll.add(42);
        ll.add(29);
        ll.add(32);
        ll.add(87);
        ll.add(53);
        ll.printNthFromEnd(4);
    }
}

倒数第 4 个节点是 29