Java solution using dummy head


  • 0
    S

    As the head may be deleted due to duplication, I introduce a dummy head, the next node of dummy head would be the new head.

    cur is the current node and next is cur.next. The case without duplication is simple. If duplication happens, move cur to next.next and try to find one node that has different value from next.val.

    public class Solution {
        public ListNode deleteDuplicates(ListNode head) {
            if (head == null || head.next == null)
                return head;
            ListNode dummy = new ListNode (-1), pre = dummy;
            for (ListNode cur = head, next = head.next; cur != null; next = cur == null ? null : cur.next) {
                if (next == null || cur.val != next.val) {
                    pre.next = cur;
                    pre = cur;
                    cur = cur.next;
                } else {
                    cur = next.next;
                    while (cur != null && cur.val == next.val)
                        cur = cur.next;
                }
            }
            pre.next = null;
            return dummy.next;
        }
    }

  • 0
    H

    a little bit confused for line 12, why do cur = next.next here?
    For example if we have a list with three same value like 1 -> 2 -> 2 -> 2 -> 3 ->4, when 'curr' point to the first 2, 'next' point to the second 2, line 12 will jump 'curr' to the third 2 and 'next' to 3. so the third 2 will be kept in the list.


Log in to reply
 

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