O(N) time O(1) space, Easiest Understanding


  • 1
    Z

    The idea is simple, we maintain two pointers, pre, cur in the given List. Pre pointer is always referring to one position before the cur pointer. When we found pre.val != cur.val && cur.val != cur.next.val, the node referred by cur pointer is a unique node.

    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) {
            return null;
        }
        
        ListNode dummy = new ListNode(0 == head.val ? 1 : 0); // to guarantee the dummy node is not same as the original head. 
    
        dummy.next = head;
        
        ListNode pre = dummy;
        ListNode cur = head;
    
        ListNode first = dummy;  // the first node in the new unduplicated(result) list.
        
        while (cur != null && cur.next != null) {
            if (cur.val != pre.val && cur.val != cur.next.val) { // we found a unique node, we connect it at the tail of the unduplicated list, and update the first node.
                first.next = cur;
                first = first.next;
            }
            pre = cur;
            cur = cur.next;
        }
        
        if (pre.val != cur.val) { // the last node needs to be dealt with independently
            first.next = cur;
            first = first.next;
        }
        
        first.next = null; // the subsequent list is duplicate.
        
        return dummy.next;
    }

  • 0
    B

    @ZhuEason I found your solution to be not only correct and efficient, but also very easy to understand. I had one question though - what made you think initialize the value of the dummy node to 1 or 0? I initialized it to -1 and got a wrong answer. Thank you!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.