Dada una lista enlazada individualmente L: L0 → L1 → … → Ln-1 → Ln,
reordenarlo a: L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …
Por ejemplo, dado {1,2,3,4}, reordenarlo a {1,4,2,3}. Debe hacer esto en el lugar sin alterar los valores de los nodos.
Solución Java
Debido a que el problema requiere operaciones «in situ», solo podemos cambiar sus punteros, no crear una nueva lista. Este problema se puede resolver siguiendo los siguientes 3 pasos:
- Rompa la lista en el medio a dos listas (use punteros rápidos y lentos)
- Invertir el orden de la segunda lista
- Fusionar dos listas nuevamente juntas
El siguiente código es una clase ejecutable completa con pruebas.
//Class definition of ListNode class ListNode { int val; ListNode next; ListNode(int x) { val = x; next = null; } } public class ReorderList { public static void main(String[] args) { ListNode n1 = new ListNode(1); ListNode n2 = new ListNode(2); ListNode n3 = new ListNode(3); ListNode n4 = new ListNode(4); n1.next = n2; n2.next = n3; n3.next = n4; printList(n1); reorderList(n1); printList(n1); } public static void reorderList(ListNode head) { if (head != null && head.next != null) { ListNode slow = head; ListNode fast = head; //use a fast and slow pointer to break the link to two parts. while (fast != null && fast.next != null && fast.next.next!= null) { //why need third/second condition? System.out.println("pre "+slow.val + " " + fast.val); slow = slow.next; fast = fast.next.next; System.out.println("after " + slow.val + " " + fast.val); } ListNode second = slow.next; slow.next = null;// need to close first part // now should have two lists: head and fast // reverse order for second part second = reverseOrder(second); ListNode p1 = head; ListNode p2 = second; //merge two lists here while (p2 != null) { ListNode temp1 = p1.next; ListNode temp2 = p2.next; p1.next = p2; p2.next = temp1; p1 = temp1; p2 = temp2; } } } public static ListNode reverseOrder(ListNode head) { if (head == null || head.next == null) { return head; } ListNode pre = head; ListNode curr = head.next; while (curr != null) { ListNode temp = curr.next; curr.next = pre; pre = curr; curr = temp; } // set head node's next head.next = null; return pre; } public static void printList(ListNode n) { System.out.println("------"); while (n != null) { System.out.print(n.val); n = n.next; } System.out.println(); } } |
Mensajes para llevar
Los tres pasos se pueden utilizar para resolver otros problemas de la lista enlazada. Los siguientes diagramas ilustran cómo funciona cada uno de los pasos.
Lista inversa:
Fusionar lista:
Tenga en cuenta que los movimientos de los punteros siempre comienzan con la asignación del siguiente nodo a una variable temporal t.
