package fundamentals.list.removal.lc082_removeduplicatefromsortedlist2;

import fundamentals.list.ListNode;

/**
 * Given a sorted linked fundamentals.list, delete all nodes that have duplicate numbers,
 * leaving only distinct numbers from the original fundamentals.list.
 * For example,
 * Given 1->2->3->3->4->4->5, return 1->2->5.
 * Given 1->1->1->2->3, return 2->3.
 */
public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) {
            return head;
        }

        // Sentinel for simplicity
        ListNode prev = new ListNode(-1);
        prev.next = head;
        head = prev;

        ListNode cur = head.next;
        boolean isDup = false;
        while (cur != null) {
            if (prev.next == cur) {
                cur = cur.next;
                continue;
            }

            if (prev.next.val == cur.val) {
                isDup = true;
            } else {
                if (isDup) {
                    prev.next = cur;
                    isDup = false;
                } else {
                    prev = prev.next;
                }
            }
            cur = cur.next;
        }

        if (isDup) {
            prev.next = null;
        }

        return head.next;
    }
}

@@ -392,16 +392,51 @@
 lution %7B
+%0A%0A    // Solution from programcreek
 %0A    pub
@@ -502,32 +502,1694 @@
 head == null) %7B%0A
+            return null;%0A        %7D%0A%0A        ListNode dummy = new ListNode(0);%0A        dummy.next = head;%0A%0A        // Invariant: nodes before prev (inclusive) have no duplicates%0A        ListNode prev = dummy;%0A        while (prev.next != null && prev.next.next != null) %7B%0A            if (prev.next.val == prev.next.next.val) %7B%0A                int dup = prev.next.val;%0A                while (prev.next != null && prev.next.val == dup) %7B // delete all duplicates%0A                    prev.next = prev.next.next;%0A                %7D%0A            %7D else %7B%0A                prev = prev.next;%0A            %7D%0A        %7D%0A        return dummy.next;%0A    %7D%0A%0A    // My 2nd: a little trivial in loop body%0A    public ListNode deleteDuplicates2(ListNode head) %7B%0A        if (head == null) %7B%0A            return null;%0A        %7D%0A%0A        ListNode dummy = new ListNode(0);%0A        dummy.next = head;%0A%0A        // Invariant: nodes before prev (inclusive) have no duplicates%0A        ListNode prev = dummy;%0A        while (prev != null && prev.next != null) %7B%0A            // Find next distinct value%0A            ListNode cur = prev.next;%0A            ListNode dup = cur.next;%0A            while (dup != null && cur.val == dup.val) %7B%0A                dup = dup.next;%0A            %7D%0A%0A            // dup is a node or null (reach end)%0A            if (dup == cur.next) %7B  // no duplicates, delete none, just move forward%0A                prev = prev.next;%0A            %7D else %7B                // found duplicates, bypass all of them%0A                prev.next = dup;%0A            %7D%0A        %7D%0A        return dummy.next;%0A    %7D%0A%0A    public ListNode deleteDuplicates3(ListNode head) %7B%0A        if (head == null) %7B%0A
             retu

leetcode-082 remove duplicate from sorted list 2