Compartilhamento de tecnologia

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

Exclua elementos duplicados na lista vinculada e mantenha um elemento duplicado

p1 p2
1 -> 1 -> 2 -> 3 -> 3 -> nulo

p1.val == p2.val então exclua p2, observe que p1 permanece inalterado neste momento

p1 p2
1 -> 2 -> 3 -> 3 -> nulo

p1.val != p2.val Então p1, p2 movem-se para trás

p1 p2
1 -> 2 -> 3 -> 3 -> nulo
         
p1 p2
1 -> 2 -> 3 -> 3 -> nulo

p1.val == p2.val então exclua p2

p1 p2
1 -> 2 -> 3 -> nulo

Quando p2 == null sai do loop

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;
}

Não retenha nenhum elemento duplicado

p1 é o nó anterior a ser excluído. Cada ciclo compara os valores de p2 e p3.

• Se os valores de p2 e p3 forem repetidos, então p3 continua a retroceder até que um nó que não seja duplicado com p2 seja encontrado, e p1 aponta para p3 para completar a exclusão.

• Se os valores de p2 e p3 não se sobrepõem, p1, p2 e p3 são deslocados para trás em uma posição e continuam a operação acima.

• p2 ou p3 é nulo, saia do loop

  • Quando p2 é nulo, por exemplo, a lista vinculada é 1 1 1 null

 

p1 p2 p3
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

p1 p3
s, 2, 3, nulo

p1 p2 p3
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;
}