Categorías
Algorithms

LeetCode – Lista de clasificación (Java)

LeetCode – Lista de clasificación:

Ordene una lista vinculada en tiempo O (n log n) utilizando una complejidad de espacio constante.

Análisis

Si este problema no tiene la limitación de espacio constante, podemos ordenar fácilmente usando un método de clasificación del SDK de Java. Con la limitación de espacio constante, necesitamos hacer alguna manipulación del puntero.

  1. Divide la lista a dos en el medio
  2. Ordene de forma recursiva las dos sublistas
  3. Fusionar las dos sublistas

Solución Java

Cuando revisé este problema en 2018, lo escribí de la siguiente manera, que es más concisa.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        if(head==null || head.next==null){
            return head;
        }
 
        //partition the list
        ListNode p1 = head;
        ListNode firstEnd = getFirstEnd(head);
        ListNode p2 = firstEnd.next;
        firstEnd.next = null;
 
        //sort each list
        p1 = sortList(p1);
        p2 = sortList(p2);
 
        //merge two lists
        return merge(p1, p2);
    }
 
    //get the list partition point
    private ListNode getFirstEnd(ListNode head){
        ListNode p1 = head;
        ListNode p2 = head;
        while(p1!=null && p2!=null){
            if(p2.next==null||p2.next.next==null){
                return p1;
            }
 
            p1 = p1.next;
            p2 = p2.next.next;
        }
 
        return head;
    }
 
    //merge two list
    private ListNode merge(ListNode n1, ListNode n2){
        ListNode head = new ListNode(0);
        ListNode p = head;
        ListNode p1 = n1;
        ListNode p2 = n2; 
        while(p1!=null && p2!=null){
            if(p1.val<p2.val){
                p.next = p1;
                p1 = p1.next;
            }else{
                p.next = p2;
                p2 = p2.next;
            }
 
            p = p.next;
        }
 
        if(p1!=null){
            p.next = p1;
        }
 
        if(p2!=null){
            p.next = p2;
        }
 
        return head.next;
    }
}
  LeetCode - Particionamiento Palindrome (Java)

Por Programación.Click

Más de 20 años programando en diferentes lenguajes de programación. Apasionado del code clean y el terminar lo que se empieza. ¿Programamos de verdad?

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *