Une liste chaînée est une structure de données linéaire où tous les nœuds sont connectés les uns aux autres en stockant l'adresse du nœud suivant. Trouver le nième nœud dans une liste chaînée signifie obtenir la valeur du nième nœud dans une liste chaînée donnée, ce qui peut être effectué par des méthodes itératives et récursives.
Given linked list: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null Node to find: 3
3
Explication : La valeur du troisième nœud est 3.
Dans cette méthode, nous parcourrons directement la liste chaînée en utilisant la boucle while jusqu'à atteindre le dernier nœud ou le nœud souhaité.
// class to create the structure of the nodes class Node{ constructor(data){ this.value = data; this.next = null; } } // function to print the linked list function print(head){ var temp = head; var ans = "" while(temp.next != null){ ans += temp.value; ans += " -> " temp = temp.next } ans += temp.value ans += " -> null" console.log(ans) } // function to add data in linked list function add(data, head, tail){ return tail.next = new Node(data); } // function to find the nth node function findNode(head, node){ var temp = head; while(node > 1 && temp != null){ node--; temp = temp.next; } return temp; } // defining linked list var head = new Node(1) var tail = head tail = add(2,head, tail) tail = add(3,head, tail) tail = add(4,head, tail) tail = add(5,head, tail) tail = add(6,head, tail) tail = add(7,head, tail) tail = add(8,head, tail) // printing linked list console.log("The given linked list is: ") print(head) // defining node to get var node = 5; // calling function to get the nth node; var nth_node = findNode(head,node) if(nth_node == null){ console.log("The given linked list does not have the Nth Node"); } else{ console.log("The value present at the nth node is: " + nth_node.value); }
The given linked list is: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> null The value present at the nth node is: 5
La complexité temporelle du code ci-dessus est O(N), où N est la taille de la liste chaînée donnée. Le nombre donné ici peut être inférieur à la taille de la liste chaînée donnée, mais dans le pire des cas, nous ne parcourrons que la longueur de la liste chaînée.
Ici, nous n'utilisons aucun espace supplémentaire, ce qui signifie que la complexité temporelle du code ci-dessus est O(1).
Dans cette méthode, nous utiliserons des appels récursifs au lieu de boucles while pour parcourir la liste chaînée et implémenter la logique précédente.
// class to create the structure of the nodes class Node{ constructor(data){ this.value = data; this.next = null; } } // function to print the linked list function print(head){ var temp = head; var ans = "" while(temp.next != null){ ans += temp.value; ans += " -> " temp = temp.next } ans += temp.value ans += " -> null" console.log(ans) } // function to add data in linked list function add(data, head, tail){ return tail.next = new Node(data); } // function to find the nth node function findNode(head, node){ if(node == 1){ return head; } else if(head == null){ return null; } else{ return findNode(head.next, node-1); } } // defining linked list var head = new Node(1) var tail = head tail = add(2,head, tail) tail = add(3,head, tail) tail = add(4,head, tail) tail = add(5,head, tail) tail = add(6,head, tail) tail = add(7,head, tail) tail = add(8,head, tail) // printing linked list console.log("The given linked list is: ") print(head) // defining node to get var node = 9; // calling function to get the nth node; var nth_node = findNode(head,node) if(nth_node == null){ console.log("The given linked list does not have the " + node + " number of nodes"); } else{ console.log("The value present at the nth node is: " + nth_node.value); }
The given linked list is: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> null The given linked list does not have the 9 number of nodes
La complexité temporelle et spatiale du code ci-dessus est la même, les deux sont O(N), où N est le nombre de nœuds dans la liste chaînée donnée. L'espace ici est dû aux appels récursifs.
Dans ce tutoriel, nous avons implémenté un programme JavaScript pour trouver le nième nœud dans une liste chaînée donnée. Si le nième nœud n'existe pas, alors nous imprimons qu'il n'existe pas, sinon nous imprimons la valeur qui existe à ce nœud. Nous avons implémenté deux méthodes, l’une itérative utilisant la boucle while et l’autre récursive. La complexité temporelle des deux est O(N), mais l'itération est meilleure car elle ne nécessite aucun espace supplémentaire.
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!