Technology Sharing

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

Delete duplicate elements in the linked list, and keep one duplicate element

p1   p2
1 -> 1 -> 2 -> 3 -> 3 -> null

p1.val == p2.val then delete p2, note that p1 remains unchanged

p1   p2
1 -> 2 -> 3 -> 3 -> null

p1.val != p2.val then p1, p2 move backwards

       p1   p2
1 -> 2 -> 3 -> 3 -> null
         
              p1   p2
1 -> 2 -> 3 -> 3 -> null   

p1.val == p2.val then delete p2

              p1   p2
1 -> 2 -> 3 -> null 

When p2 == null, exit the loop

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

No duplicate elements are retained.

p1 is the previous node to be deleted, and the values ​​of p2 and p3 are compared in each loop.

• If the values ​​of p2 and p3 are repeated, p3 will continue to move backward until a node that does not repeat with p2 is found, and p1 points to p3 to complete the deletion.

• If the values ​​of p2 and p3 are not repeated, p1, p2, and p3 are shifted backwards by one position, and the above operation is continued.

• If p2 or p3 is null, exit the loop

  • When p2 is null, for example, the linked list is 1 1 1 null

 

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

p1 p3
s,   2, 3, null

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