Compartir tecnología

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Eliminar elementos duplicados en la lista vinculada y conservar un elemento duplicado

pág. 1 pág. 2
1 -> 1 -> 2 -> 3 -> 3 -> nulo

p1.val == p2.val luego elimine p2, tenga en cuenta que p1 permanece sin cambios en este momento

pág. 1 pág. 2
1 -> 2 -> 3 -> 3 -> nulo

p1.val != p2.val Luego p1, p2 retroceden

pág. 1 pág. 2
1 -> 2 -> 3 -> 3 -> nulo
         
pág. 1 pág. 2
1 -> 2 -> 3 -> 3 -> nulo

p1.val == p2.val luego elimina p2

pág. 1 pág. 2
1 -> 2 -> 3 -> nulo

Cuando p2 == null sale del bucle

código

public ListNode deleteDuplicates(ListNode head) {
    // 链表节点 < 2
    if (head == null || head.next == null) {
        return head;
    }
    // 链表节点 >= 2
    ListNode p1 = head;
    ListNode p2;
    while ((p2 = p1.next) != null) {
        if (p1.val == p2.val) {
            p1.next = p2.next;
        } else {
            p1 = p1.next;
        }
    }
    return head;
}

No conserve ningún elemento duplicado

p1 es el nodo anterior que se eliminará. Cada ciclo compara los valores de p2 y p3.

• Si los valores de p2 y p3 se repiten, entonces p3 continúa retrocediendo hasta que se encuentra un nodo que no está duplicado con p2 y p1 apunta a p3 para completar la eliminación.

• Si los valores de p2 y p3 no se superponen, p1, p2 y p3 se desplazan hacia atrás una posición y continúan la operación anterior.

• p2 o p3 es nulo, salga del ciclo

  • Cuando p2 es nulo, por ejemplo, la lista enlazada es 1 1 1 nula

 

pág. 1 pág. 2 pág. 3
s, 1, 1, 1, 2, 3, nulo

p1 p2 p3
s, 1, 1, 1, 2, 3, nulo

p1 p2 p3
s, 1, 1, 1, 2, 3, nulo

pág. 1 pág. 3
s, 2, 3, nulo

pág. 1 pág. 2 pág. 3
s, 2, 3, nulo

p1 p2 p3
s, 2, 3, nulo

código

public ListNode deleteDuplicates(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
 
    ListNode s = new ListNode(-1, head);
    ListNode p1 = s;
    ListNode p2;
    ListNode p3;
    while ((p2 = p1.next) != null && (p3 = p2.next) != null) {
        if (p2.val == p3.val) {
            while ((p3 = p3.next) != null 
                   && p3.val == p2.val) {
            }
            p1.next = p3;
        } else {
            p1 = p1.next;
        }
    }
    return s.next;
}