[LeetCode#83]Remove Duplicates from Sorted List

When sovling linkedlist problems, two boundary cases needed to be very carefully treated, otherwise it may result in head lossing or get null pointer exception. 

1. the head node might be changed. 

Thus we may lose the information for new result linked list. One classic way is to use a dummy node to always pointer the the head the list. 

In this problem, when duplicates appear, we would keep one copy. Thus the head node could never be changed, we won't need to set a dummy head for this case.



2. If we have a scaner over the linkedlist, or several scanner(which we only need to consider the faster scanner). 

The usually checking condition when traversaling the list is "while (faster != null)", In this case, we could only guarantee at the moment of entering the while loop, the faster is not null pointer. However, we may move the faster in the while loop:

like:

while (faster != null && ptr1.val == faster.val) {

    faster = faster.next;

}

the faster may reach the end of the list, thus faster is null.

if we have a statement: "fast = faster.next" without any checking, it would result in a null pointer exception. 



???if we add a checking over here, it seems to distort the logic !

In fact, the boundary case is the ending procedure over the list, after it, the invariant is over, we would not need to care about that!!!

     　　if (head == null)

            return null;

        ListNode ptr1 = head;

        ListNode ptr2 = head.next;

        

        while (ptr2 != null) {

            while (ptr2 != null && ptr1.val == ptr2.val) {

                ptr2 = ptr2.next;

            }

            ptr1.next = ptr2;

            ptr1 = ptr2;

            if (ptr2 != null) //may directly reach the end

                ptr2 = ptr2.next;

        }

        return head;

public class Solution {

    public ListNode deleteDuplicates(ListNode head) {

        if (head == null)

            return null;

        ListNode dummy = new ListNode(0);

        ListNode pre = dummy;

        ListNode cur = head;

        while (cur != null) {

            if (pre == dummy || pre.val != cur.val) {

                pre.next = cur;

                pre = cur;

            }

            cur = cur.next;

        }

        pre.next = null; //remember the last step!!!

        return dummy.next;

    }

}