Dada una lista vinculada, invierta los nodos de una lista vinculada k a la vez y devuelva su lista modificada. Si el número de nodos no es un múltiplo de k, los nodos excluidos al final deberían permanecer como están. No puede alterar los valores en los nodos, solo se pueden cambiar los nodos en sí.
Por ejemplo,
Given this linked list: 1->2->3->4->5 For k = 2, you should return: 2->1->4->3->5 For k = 3, you should return: 3->2->1->4->5
Solución Java
public ListNode reverseKGroup(ListNode head, int k) { if(head==null||k==1) return head; ListNode fake = new ListNode(0); fake.next = head; ListNode prev = fake; int i=0; ListNode p = head; while(p!=null){ i++; if(i%k==0){ prev = reverse(prev, p.next); p = prev.next; }else{ p = p.next; } } return fake.next; } |
public ListNode reverse(ListNode prev, ListNode next){ ListNode last = prev.next; ListNode curr = last.next; while(curr != next){ last.next = curr.next; curr.next = prev.next; prev.next = curr; curr = last.next; } return last; } |
Podemos escribir el método inverso de manera diferente como se muestra a continuación. Yo personalmente es más comprensible.
private ListNode reverse(ListNode prev, ListNode next){ ListNode p1 = prev.next; ListNode p2 = p1.next; while(p2 != next){ ListNode t = p2.next; p2.next = p1; p1 = p2; p2 = t; } ListNode rNode = prev.next; prev.next.next = next; prev.next = p1; return rNode; } |
