Dada una lista vinculada, intercambie cada dos nodos adyacentes y devuelva su encabezado.
Por ejemplo, dado 1-> 2-> 3-> 4, debe devolver la lista como 2-> 1-> 4-> 3.
Su algoritmo debe usar solo espacio constante. No puede modificar los valores de la lista, solo se pueden cambiar los nodos.
Solución Java 1
Utilice dos variables de plantilla para rastrear el nodo anterior y siguiente de cada par.
public ListNode swapPairs(ListNode head) { if(head == null || head.next == null) return head; ListNode h = new ListNode(0); h.next = head; ListNode p = h; while(p.next != null && p.next.next != null){ //use t1 to track first node ListNode t1 = p; p = p.next; t1.next = p.next; //use t2 to track next node of the pair ListNode t2 = p.next.next; p.next.next = p; p.next = t2; } return h.next; } |
Solución Java 2
Cada vez que hago el mismo problema, a menudo obtengo diferentes soluciones. Aquí hay otra forma de escribir esta solución.
public ListNode swapPairs(ListNode head) { if(head==null || head.next==null) return head; //a fake head ListNode h = new ListNode(0); h.next = head; ListNode p1 = head; ListNode p2 = head.next; ListNode pre = h; while(p1!=null && p2!=null){ pre.next = p2; ListNode t = p2.next; p2.next = p1; pre = p1; p1.next = t; p1 = p1.next; if(t!=null) p2 = t.next; } return h.next; } |
