Java-program til at finde n'te node fra slutningen af ​​linket liste

I denne vejledning vil vi se, hvordan du finder den n'te node fra slutningen af ​​den sammenkædede liste i java. LinkedList er en lineær datastruktur, hvor elementerne ikke er gemt på sammenhængende steder, og hvert element er et separat objekt med en datadel og adressedel. Hvert element er kendt som en node. På grund af dynamikken og lette indsættelser og sletninger foretrækkes de frem for arrays. Men før du går videre, hvis du ikke er bekendt med konceptet med den linkede liste i java, så tjek artiklen om Linked List i Java.

Input: Indtast elementerne på den linkede liste:6 7 8 4 5 1 3 2 5

Output: Den 6. node fra slutningen af ​​den linkede liste er:4

Dette kan gøres ved at bruge følgende metoder:

Fremgangsmåde 1:Brug af længden af ​​den linkede liste.

Fremgangsmåde 2:Brug af Two pointers-konceptet.

Lad os se på hver af disse tilgange for en bedre forståelse.

Program 1:Java-program til at finde den n'te node fra slutningen af ​​LinkedList

I dette program vil vi se, hvordan man finder den n'te node fra slutningen af ​​den linkede liste i java ved at bruge længden af ​​den linkede liste.

Algorithme:

1. Start
2. Opret en linket liste over strengtyper ved hjælp af den linkede listedatastruktur.
3. Tilføj nu noder til den linkede liste.
4. Kald en brugerdefineret funktion for at beregne den n'te node fra slutningen af ​​den sammenkædede liste.
5. Beregn først længden af ​​den linkede liste.
6. Udskriv nu den (længde – n + 1) node fra begyndelsen af ​​den linkede liste.
7. Stop

Lad os se på nedenstående eksempel for en bedre forståelse af ovenstående algoritme.

//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. node fra slutningen er 27

Program 2:Java-program til at finde den n'te node fra slutningen af ​​LinkedList

I dette program vil vi se, hvordan man finder den n'te node fra slutningen af ​​den linkede liste i java ved at bruge to pointere.

Algorithme:

1. Start
2. Opret en linket liste over strengtyper ved hjælp af den linkede listedatastruktur.
3. Tilføj nu noder til den linkede liste.
4. Kald en brugerdefineret funktion for at beregne den n'te node fra slutningen af ​​den sammenkædede liste.
5. Deklarer to pointere:pointer1 og pointer2.
6. Initialiser begge pointer to head.
7. Først skal du flytte den første markør til n noder fra hovedet.
8. Flyt nu begge markører én efter én, indtil referencemarkøren når enden.
9. Nu vil den anden markør pege på den n'te node fra enden.
10. Return den anden markør.
11. Vis resultatet.
12. Stop

Lad os se på nedenstående eksempel for en bedre forståelse af ovenstående algoritme.

//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. node fra den sidste er 29