Escribí el siguiente código para revertir una lista vinculada, pero no estoy seguro de lo que estoy haciendo incorrectamente. Esto es de un problema de muestra aquí que pide invertir una lista enlazada.
/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @return {ListNode} */ var reverseList = function(head) { function traverse(node) { if(!node.next) return node; else { let currentNode = node.next; let nextNode = traverse(node.next); nextNode.next = currentNode; return nextNode; } } return traverse(head); }; Para la entrada dada, [4,5] , cuando intento ejecutarlo dice Error - Found cycle in the ListNode . ¿Podría alguien explicar qué estoy haciendo mal aquí?
El problema aquí es que siempre está devolviendo el último nodo de la lista enlazada en traverse(node.next) que luego cambia al siguiente y hace que se forme un bucle.
Considere una lista enlazada, 1 -> 2 -> 3 -> 4.
Las llamadas recursivas son:
traverse(1) -> traverse(2) -> traverse(3) -> traverse(4)
atravesar(4) - devuelve 4.
traverse(3) - 4.next=3 y devuelve 4.
traverse(2) - 4.next=2 y devuelve 4.
traverse(1) - 4.next=1 y devuelve 4.
Por lo tanto, se forma una lista enlazada cíclica: 1->2->3->4->1...
En su lugar, debe cambiar el siguiente en su lugar durante la llamada transversal, similar a esto:
var reverseList = function(head) { function traverse(node) { if(!node || !node.next) return node; else { let currentNode = node; let nextNode = node.next; let head = traverse(node.next); nextNode.next = currentNode; currentNode.next = null; return head; } } return traverse(head); };No veo por qué necesitamos recursividad aquí. Solo necesitamos realizar un seguimiento del siguiente nodo para modificar y el encabezado de la nueva lista. Me gusta:
var reverseList = function(head) { let newHead = null; while (head) { const node = head; head = node.next; node.next = newHead; newHead = node; } return newHead; };El problema es que no head.next , todavía apunta al segundo nodo (ahora penúltimo). Podrías arreglar esto haciendo
const last = traverse(head); last.next = null; return last;pero este código todavía tiene errores, ya que solo puede manejar listas no vacías, y en realidad probablemente no debería mutar la lista de argumentos en absoluto, sino producir una nueva. Ese estilo inmutable también es mucho, mucho más simple:
/** * @param {ListNode} head * @return {ListNode} */ function reverseList(head) { function traverse(node, tail) { if (!node) return tail; else return traverse(node.next, new ListNode(node.val, tail)); } return traverse(head, null); }