Java >> Tutoriel Java >  >> Java

Inverser une structure de données de liste liée en Java

Liste liée ou liste chaînée unique est un type de structure de données. Dans une  liste liée , chaque nœud stocke le contenu et un pointeur (référence) du nœud suivant. Inverser une liste liée est important pour comprendre la flexibilité et la convivialité de la liste liée.

Question :

Étant donné le pointeur vers le nœud principal d'une liste chaînée, la tâche consiste à inverser la liste chaînée. Vous devez inverser la liste en modifiant les liens entre les nœuds.

Exemple :

Liste chaînée donnée :-> 4-> 2-> 7-> 9-> 1
Liste chaînée inversée :-> 1-> 9-> 7-> 2-> 4

Solutions : Méthode itérative

1. Initialiser trois pointeurs

currentNode = head; nextNode = null; previousNode = null;

2. Parcourez la liste chaînée. Dans la boucle while, procédez comme suit.

//stocker le nœud suivant
currentNode = currentNode->nextNode

// Inverse les pointeurs de nœud

currentNode -> next = previousNode 

// Avancer d'un pas le nœud précédent et actuel
previousNode = currentNode
currentNode = nextNode

Code terminé :

package in.eyehunt.data.struc;

public class LinkedList {

    Node head; // head of list

    // Linked list Node.
    class Node {
        int data;
        Node next;

        // Parameterized constructor
        Node(int d) {
            data = d;
            next = null;
        }
    }

    void push(int n) {
        //create new node
        Node newNode = new Node(n);
        // next node is head
        newNode.next = head;
        // move had point to new node
        head = newNode;
    }

    void reverseLinkedList() {

        Node currentNode = head;
        Node nextNode = null;
        Node previousNode = null;
        while (currentNode !=null){
            nextNode = currentNode.next;
            currentNode.next = previousNode;
            previousNode = currentNode;
            currentNode = nextNode;
        }
        head = previousNode;
        printAllNodes("\nReverse Linked list : ");
    }

    void printAllNodes(String mesg) {
        Node node = head;
        System.out.print(mesg);
        while (node != null) {
            System.out.print("-> " + node.data);
            node = node.next;
        }
    }

    public static void main(String a[]) {
        //create a simple linked list with 4 nodes
        LinkedList linkedList = new LinkedList();
        linkedList.push(1);
        linkedList.push(9);
        linkedList.push(7);
        linkedList.push(2);
        linkedList.push(4);
        linkedList.printAllNodes("Given Linked list : ");
        linkedList.reverseLinkedList();
    }
}

Complexité temporelle : O(n)
Complexité spatiale : O(1)

Inverser une liste liée est en tête de liste des questions d'entretien Java, alors entraînez-vous davantage… voici d'autres questions d'entretien LinkedList :

  1. Programmer le nième nœud à partir de la fin d'une liste chaînée
  2. Trouver le milieu d'une structure de données de liste chaînée donnée
  3. Insérer un nouveau nœud dans une structure de données de liste chaînée
  4. Trouver la longueur d'une structure de données de liste chaînée (itérative et récursive)

Balise Java