Java >> Tutoriel Java >  >> Java

Programme Java pour inverser une liste chaînée par paires

Dans ce tutoriel, nous allons voir comment inverser une liste chaînée par paires 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.

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

Sortie : Avant d'inverser la liste chaînée :6 7 8 9 5

Après avoir inversé la liste chaînée :7 6 9 8 3 5

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

Approche 1 :par itération

Approche 2 :par récursivité

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

Programme 1 :Programme Java pour inverser une liste chaînée par paires

Dans ce programme, nous verrons comment inverser une liste chaînée par paires en java en utilisant l'approche itérative.

Algorithme :

  1. Démarrer
  2. Déclarer une liste chaînée de types entiers sans aucune taille initiale.
  3. Utilisez la méthode add pour ajouter les éléments.
  4. Ajoutez les éléments à la fin de la liste.
  5. Imprimez les éléments de la liste liée avant de les inverser.
  6. Liez d'abord deux nœuds correctement, puis échangez-les.
  7. Comme le lien précédent est rompu, reliez à nouveau les nœuds.
  8. Imprimer les éléments de la liste liée après l'inversion.
  9. Arrêter

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

//Java Program to Reverse a linked list in Pairs
public class ReverseLinkedListInPair
{
    private Node head;
    private static class Node 
    {
        private int value;
        private Node next;
        Node(int value) {
            this.value = value;
        }
    }
    public void addLast(Node node) {
        if (head == null) {
            head = node;
        } else {
            Node temp = head;
            while (temp.next != null)
                temp = temp.next;
            temp.next = node;
        }
    }
    public void printLinkedList(Node head) {
        Node temp = head;
        while (temp != null) {
            System.out.format("%d ", temp.value);
            temp = temp.next;
        }
        System.out.println();
    }
    // Reverse the linked list in pair
    public static Node reverseLLInPairs(Node head) 
    {
        Node current=head;
        Node temp=null;
        Node newHead =null;
        while (current != null && current.next != null) 
        {
            if (temp != null) 
            {
                temp.next.next = current.next;
            }
            temp=current.next;     
            current.next=temp.next;
            temp.next=current;
            if (newHead == null)
                newHead = temp;
            current=current.next;
        }     
        return newHead;
    }
    //Driver Code
    public static void main(String[] args) {
        ReverseLinkedListInPair li = new ReverseLinkedListInPair();
        // Creating a linked list
        Node head=new Node(0);
        li.addLast(head);
        li.addLast(new Node(1));
        li.addLast(new Node(2));
        li.addLast(new Node(3));
        li.addLast(new Node(4));
        li.addLast(new Node(5));
        System.out.println("Before reversing in pair: ");
        li.printLinkedList(head);
        //Reversing LinkedList in pairs
        Node result=reverseLLInPairs(head);
        System.out.println("After reversing in pair: ");
        li.printLinkedList(result);
    }
}


Avant inversion par paire :
0 1 2 3 4 5
Après inversion par paire :
1 0 3 2 5 4

Programme 2 :Programme Java pour inverser la LinkedList par paires

Dans ce programme, nous verrons comment inverser une liste chaînée par paires en java en utilisant l'approche récursive.

Algorithme :

  1. Démarrer
  2. Déclarer une liste chaînée de types entiers sans aucune taille initiale.
  3. Utilisez la méthode add pour ajouter les éléments.
  4. Ajoutez les éléments à la fin de la liste.
  5. Imprimez les éléments de la liste liée avant de les inverser.
  6. Liez d'abord deux nœuds correctement, puis appelez la fonction récursive pour échanger les éléments.
  7. Comme le lien précédent est rompu, reliez à nouveau les nœuds.
  8. Imprimer les éléments de la liste liée après l'inversion.
  9. Arrêter

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

//Java Program to Reverse a linked list in Pairs
public class ReverseLinkedListInPair
{
    private Node head;
    private static class Node 
    {
        private int value;
        private Node next;
        Node(int value) {
            this.value = value;
        }
    }
    public void addLast(Node node) {
        if (head == null) {
            head = node;
        } else {
            Node temp = head;
            while (temp.next != null)
                temp = temp.next;
            temp.next = node;
        }
    }
    public void printLinkedList(Node head) {
        Node temp = head;
        while (temp != null) {
            System.out.format("%d ", temp.value);
            temp = temp.next;
        }
        System.out.println();
    }
    // Reverse the linked list in pair
    public static Node reverseLLInPairs(Node head) 
    {
        if (head == null || head.next == null) {
          return head;
      }
      Node temp=head.next;
      head.next=temp.next;
      temp.next=head;
      head.next=reverseLLInPairs(head.next);
      return temp;
    }
    //Driver Code
    public static void main(String[] args) {
        ReverseLinkedListInPair li = new ReverseLinkedListInPair();
        // Creating a linked list
        Node head=new Node(0);
        li.addLast(head);
        li.addLast(new Node(1));
        li.addLast(new Node(2));
        li.addLast(new Node(3));
        li.addLast(new Node(4));
        li.addLast(new Node(5));
        System.out.println("Before reversing in pair: ");
        li.printLinkedList(head);
        //Reversing LinkedList in pairs
        Node result=reverseLLInPairs(head);
        System.out.println("After reversing in pair: ");
        li.printLinkedList(result);
    }
}


Avant inversion par paire :
0 1 2 3 4 5
Après inversion par paire :
1 0 3 2 5 4


Balise Java