Java >> Tutoriel Java >  >> Java

Programme Java pour trouver le nième nœud à partir de la fin de la liste chaînée

Java

Dans ce tutoriel, nous verrons comment trouver le nième nœud à partir de la fin de la liste chaînée en java. LinkedList est une structure de données linéaire où les éléments ne sont pas stockés dans des emplacements contigus et chaque élément est un objet séparé avec une partie données et une partie adresse. Chaque élément est appelé nœud. En raison de la dynamique et de la facilité des insertions et des suppressions, ils sont préférés aux tableaux. Mais avant d'aller plus loin, si vous n'êtes pas familier avec le concept de liste chaînée en Java, consultez l'article sur la liste chaînée en Java.

Entrée : Saisissez les éléments de la liste chaînée :6 7 8 4 5 1 3 2 5

Sortie : Le 6ème nœud à partir de la fin de la liste chaînée est :4

Cela peut être fait en utilisant les méthodes suivantes :

Approche 1 :Utilisation de la longueur de la liste chaînée.

Approche 2 :Utilisation du concept à deux pointeurs.

Examinons chacune de ces approches pour une meilleure compréhension.

Programme 1 :Programme Java pour trouver le nième nœud à partir de la fin de LinkedList

Dans ce programme, nous verrons comment trouver le nième nœud à partir de la fin de la liste chaînée en java en utilisant la longueur de la liste chaînée.

Algorithme :

  1. Démarrer
  2. Créez une liste liée de types de chaînes à l'aide de la structure de données de la liste liée.
  3. Ajoutez maintenant des nœuds à la liste liée.
  4. Appelez une fonction définie par l'utilisateur pour calculer le nième nœud à partir de la fin de la liste liée.
  5. Tout d'abord, calculez la longueur de la liste liée.
  6. Maintenant, imprimez le (longueur - n + 1)ème nœud à partir du début de la liste chaînée.
  7. Arrêter

Regardons l'exemple ci-dessous pour une meilleure compréhension de l'algorithme ci-dessus.

//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);
	}
}


Le 6e nœud à partir de la fin est 27

Programme 2 :Programme Java pour trouver le nième nœud à partir de la fin de LinkedList

Dans ce programme, nous allons voir comment trouver le nième nœud à partir de la fin de la liste chaînée en java en utilisant deux pointeurs.

Algorithme :

  1. Démarrer
  2. Créez une liste liée de types de chaînes à l'aide de la structure de données de la liste liée.
  3. Ajoutez maintenant des nœuds à la liste liée.
  4. Appelez une fonction définie par l'utilisateur pour calculer le nième nœud à partir de la fin de la liste liée.
  5. Déclarez deux pointeurs :pointer1 et pointer2.
  6. Initialiser les deux pointeurs vers head.
  7. Tout d'abord, déplacez le premier pointeur vers n nœuds à partir de la tête.
  8. Déplacez maintenant les deux pointeurs un par un jusqu'à ce que le pointeur de référence atteigne la fin.
  9. Maintenant, le deuxième pointeur pointe vers le nième nœud à partir de la fin.
  10. Renvoyer le deuxième pointeur.
  11. Afficher le résultat.
  12. Arrêter

Regardons l'exemple ci-dessous pour une meilleure compréhension de l'algorithme ci-dessus.

//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);
	}
}


Le 4ème nœud à partir du dernier est le 29


Balise Java