Java >> Tutoriel Java >  >> Java

Trouver le milieu d'une structure de données de liste chaînée donnée

Question :Dans une liste chaînée donnée, trouvez le milieu de la liste et imprimez le numéro.

Entrée :-> 4-> 2-> 7-> 9-> 1

Sortie :7

Avant de commencer, vous devez connaître la liste liée et comment la créer et insérer un nœud (données) dans LinkedList.

Il existe de nombreuses approches pour trouver le numéro du milieu dans LinkedList.

1. Approche à pointeur unique

Dans cette approche, nous allons scanner toute la liste et compter le nombre de nœuds. Nous divisons le nombre par 2, puis parcourons à nouveau la liste jusqu'à ce nœud.

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 findMiddleNode() {
        if (head == null) {
            System.out.println("LinkedList is null");
        } else {
            int middleNode = (count() % 2 == 0) ? (count() / 2) : ((count() + 1) / 2);

            Node pointerNode = head;
            int countNodes = 0;
            while (countNodes != middleNode -1) {
                pointerNode = pointerNode.next;
                countNodes ++;
            }
            System.out.println("\nMiddle node of linked List is " + middleNode);
            System.out.println("Middle node data is " + pointerNode.data);
        }
    }
    //Returns count of nodes in linked list (iteration)
    public int count() {
        int a = 0;
        Node n = head;
        while (n != null) {
            n = n.next;
            a++;
        }
        return a;
    }
    void printAllNodes() {
        Node node = head;
        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();
        linkedList.findMiddleNode();
    }
}

Sortie :-> 4-> 2-> 7-> 9-> 1
Le nœud central de la liste liée est 3
Les données du nœud intermédiaire sont 7

Time Complexity: Time for finding the length of list + Time for locating middle node = O(n) + O(n) ≈ O(n)
Space Complexity: O(1)

2. Utilisation de 2 pointeurs

Avec 2 pointeurs pour parcourir la liste, nous pouvons trouver le milieu de la liste avec un seul balayage sur la liste liée.

  • pointer1 parcourt un nœud à la fois
  • pointe2 parcourt deux nœuds à la fois.

Ainsi, lorsque pointe2 atteint la fin de la liste chaînée, pointer1 pointera au milieu de la liste liée.

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 findMiddleNode() {
        if (head == null) {
            System.out.println("LinkedList is null");
        } else {
            Node pointer1 = head;
            Node pointer2 = head;

            while (pointer2 != null && pointer2.next != null) {
                pointer1 = pointer1.next;
                pointer2 = pointer2.next.next;
            }
            System.out.println("\nMiddle node data is " + pointer1.data);
        }
    }
    void printAllNodes() {
        Node node = head;
        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();
        linkedList.findMiddleNode();
    }
}

Sortie : -> 4-> 2-> 7-> 9-> 1
Les données du nœud intermédiaire sont 7

Time Complexity: O(n)
Space Complexity: O(1)

voici d'autres questions d'entretien LinkedList :

  1. Programme pour trouver le nième nœud à partir de la fin d'une liste chaînée
  2. Inverser une structure de données de liste chaînée en Java
  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