Problema
Dada una lista enlazada individualmente, agrupe todos los nodos impares seguidos de los nodos pares. Tenga en cuenta que aquí estamos hablando del número de nodo y no del valor en los nodos.
El programa debe ejecutarse en O (1) complejidad espacial y O (nodos) complejidad temporal.
Ejemplo:
Given 1->2->3->4->5->NULL, return 1->3->5->2->4->NULL.
Análisis
Este problema se puede resolver utilizando dos punteros. Iteramos sobre el enlace y movemos los dos punteros.
Solución Java
public ListNode oddEvenList(ListNode head) { if(head == null) return head; ListNode result = head; ListNode p1 = head; ListNode p2 = head.next; ListNode connectNode = head.next; while(p1 != null && p2 != null){ ListNode t = p2.next; if(t == null) break; p1.next = p2.next; p1 = p1.next; p2.next = p1.next; p2 = p2.next; } p1.next = connectNode; return result; } |
