Java concise iterative 1 ms O(n) time O(1) space


  • 0

    The idea is pretty simple: why delete the nodes from the list and keep track of duplicates, which is tricky to do as we modify the list in the process, when we can build a new list instead?

    So I just traverse the list, adding the node if it's unique. The check is pretty simple: it must not be equal to its neighbors, assuming there are any. Then just return the resulting list.

    public ListNode deleteDuplicates(ListNode head) {
        ListNode sentinel = new ListNode(0), tail = sentinel;
        for (ListNode node = head, prev = null; node != null; prev = node, node = node.next) {
            if ((prev == null || prev.val != node.val) && (node.next == null || node.next.val != node.val)) {
                tail.next = node;
                tail = node;
            }
        }
        tail.next = null;
        return sentinel.next;
    }

  • 0

    Why is this O(1) space?


  • 0

    Because the additional memory is limited to just one sentinel node and four references. So the space doesn't depend on the list size, and hence it's O(1). Well, strictly speaking, it's O(log N) because references are O(log N) by themselves, but then again there is no such thing as true O(1) space for most problems. Even if you use a single integer, it's O(log N) already! But it's customary to consider such things O(1) nevertheless.


  • 0

    Sorry I thought you created a new node.
    Anyway this code is very, very hard to understand :)


  • 0

    I created a new node, but only to act as a sentinel. But one node is still just one node. “One” doesn't depend on N. It's certainly not the easiest-to-understand code, but I don't think it's that hard either. I totally forgot about it and yet, when I looked at it to answer your question, I was able to understand it in about a minute. It reads as: create a new list, iterate over the original list (keeping track of the next/previous nodes), if the node is not equal to its parents (don't forget to handle the nulls here), add it to the new list. Terminate the new list and return it. That's it.


Log in to reply
 

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