Dada una lista vinculada, elimine el n-ésimo nodo del final de la lista y devuelva su encabezado.
Por ejemplo, dada la lista enlazada 1-> 2-> 3-> 4-> 5 yn = 2, el resultado es 1-> 2-> 3-> 5.
Solución 1 de Java: dos pasos ingenuos
Calcula primero la longitud y luego quita la enésima del principio.
public ListNode removeNthFromEnd(ListNode head, int n) { if(head == null) return null; //get length of list ListNode p = head; int len = 0; while(p != null){ len++; p = p.next; } //if remove first node int fromStart = len-n+1; if(fromStart==1) return head.next; //remove non-first node p = head; int i=0; while(p!=null){ i++; if(i==fromStart-1){ p.next = p.next.next; } p=p.next; } return head; } |
Solución Java 2: una sola pasada
Utilice punteros rápidos y lentos. El puntero rápido está n pasos por delante del puntero lento. Cuando el ayuno llega al final, el puntero lento apunta al elemento anterior del elemento de destino.
public ListNode removeNthFromEnd(ListNode head, int n) { if(head == null) return null; ListNode fast = head; ListNode slow = head; for(int i=0; i<n; i++){ fast = fast.next; } //if remove the first node if(fast == null){ head = head.next; return head; } while(fast.next != null){ fast = fast.next; slow = slow.next; } slow.next = slow.next.next; return head; } |
