力扣之有序链表去重

删除链表中的重复元素，重复元素保留一个

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

p1.val == p2.val 那么删除 p2，注意 p1 此时保持不变

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

p1.val != p2.val 那么 p1，p2 向后移动

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

p1.val == p2.val 那么删除 p2

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

当 p2 == null 退出循环

 代码

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

重复元素一个也不保留

p1 是待删除的上一个节点，每次循环对比 p2、p3 的值

• 如果 p2 与 p3 的值重复，那么 p3 继续后移，直到找到与 p2 不重复的节点，p1 指向 p3 完成删除

• 如果 p2 与 p3 的值不重复，p1，p2，p3 向后平移一位，继续上面的操作

• p2 或 p3 为 null 退出循环

  • p2 为 null 的情况，比如链表为 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

代码 

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