Dada una lista enlazada y un valor x, divídala de modo que todos los nodos menores que x vengan antes que los nodos mayores o iguales ax.
Debe conservar el orden relativo original de los nodos en cada una de las dos particiones.
Por ejemplo, dado 1-> 4-> 3-> 2-> 5-> 2 y x = 3, devuelve 1-> 2-> 2-> 4-> 3-> 5.
Solución Java
public class Solution { public ListNode partition(ListNode head, int x) { if(head == null) return null; ListNode fakeHead1 = new ListNode(0); ListNode fakeHead2 = new ListNode(0); fakeHead1.next = head; ListNode p = head; ListNode prev = fakeHead1; ListNode p2 = fakeHead2; while(p != null){ if(p.val < x){ p = p.next; prev = prev.next; }else{ p2.next = p; prev.next = p.next; p = prev.next; p2 = p2.next; } } // close the list p2.next = null; prev.next = fakeHead2.next; return fakeHead1.next; } } |