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 :
- Programme pour trouver le nième nœud à partir de la fin d'une liste chaînée
- Inverser une structure de données de liste chaînée en Java
- Insérer un nouveau nœud dans une structure de données de liste chaînée
- Trouver la longueur d'une structure de données de liste chaînée (itérative et récursive)