Technologieaustausch

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

Löschen Sie doppelte Elemente in der verknüpften Liste und behalten Sie ein doppeltes Element bei

Seite 1
1 -> 1 -> 2 -> 3 -> 3 -> null

p1.val == p2.val und dann p2 löschen. Beachten Sie, dass p1 zu diesem Zeitpunkt unverändert bleibt

Seite 1
1 -> 2 -> 3 -> 3 -> null

p1.val != p2.val Dann bewegen sich p1, p2 rückwärts

Seite 1
1 -> 2 -> 3 -> 3 -> null
         
Seite 1
1 -> 2 -> 3 -> 3 -> null

p1.val == p2.val, dann p2 löschen

Seite 1
1 -> 2 -> 3 -> null

Wenn p2 == null ist, wird die Schleife verlassen

Code

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

Behalten Sie keine doppelten Elemente bei

p1 ist der vorherige zu löschende Knoten. Jeder Zyklus vergleicht die Werte von p2 und p3.

• Wenn die Werte von p2 und p3 wiederholt werden, bewegt sich p3 weiter zurück, bis ein Knoten gefunden wird, der nicht mit p2 dupliziert wird, und p1 zeigt auf p3, um den Löschvorgang abzuschließen.

• Wenn sich die Werte von p2 und p3 nicht überlappen, werden p1, p2 und p3 um eine Position nach hinten verschoben und der obige Vorgang wird fortgesetzt.

• p2 oder p3 ist null, verlassen Sie die Schleife

  • Wenn p2 beispielsweise null ist, ist die verknüpfte Liste 1 1 1 null

 

Seite 1 Seite 2 Seite 3
s, 1, 1, 1, 2, 3, null

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

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

Seite 1 von 3
s, 2, 3, null

Seite 1 Seite 2 Seite 3
s, 2, 3, null

p1 p2 p3
s, 2, 3, null

Code

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