Removing Duplicates from linked list. Why are the position of "prev = head" and "p2 = p2.next" not outside the else statement?

user_12820757 0
Viewed 64

For the first function, shouldn't "prev = head" be outside of else because we want to set the previous every time before we change the head value?

For the second function, shouldn't "p2 = p2.next" be outside of else because we want to go next every time?

Thank you guys.


    //This would take O(n) but would require extra space O(n)
    public static Node removeDuplicates(Node head){
        Node prev = null;
        Set<Integer> hs = new HashSet<Integer>();
        
        while(head!= null){
            if(hs.contains(head.data)){
                prev.next = head.next;
            }
            else{
                hs.add(head.data);
                //why is prev = head here instead of out of the else statement? 
                prev = head;
            }
            head = head.next;
        }
        return head;
    }

    //This would take O(n^2) but no extra space is required.
    public static Node removeDuplicatesTradeOff(Node head){
        //pointer 1 and pointer 2.
        Node p1 = head;

        while(p1.next != null){
            Node p2 = p1;
            while(p2.next != null){
                if(p1.data == p2.next.data){
                    p2.next = p2.next.next;
                }
                else{
                    //why is p2 = p2.next here instead of out of the else statement? 
                    p2 = p2.next;
                }  
            }
            p1 = p1.next;
        }

        return head;
    }
singly-linked-list linked-list java
3 Answers

Shouldn't "p2 = p2.next" be outside of else because we want to go next every time

I think it would be more accurate to say that we want to have a different next available every time, instead of saying that we want to "go next" every time.

We don't always want to "go next". When prev.next has changed due to another operation (in this case removal of a duplicate) we want to stay where we are, because prev.next has already changed and is now pointing to a node further ahead (because a duplicate node has just been removed).

In other words, we don't want to have a different prev every time, we just want to have a different prev.next every time. So as long as prev.next advances every time, we don't care if prev stays the same sometimes.

That's why in both methods prev (or p2) only advances in the else branch, while prev.next (or p2.next) is updated (advances) only in the if branch.

Think of these two as different operations, the else branch being "go next" and the if branch being "drop next". When you drop a node ahead of you, you did not move (true!), but since you did drop one node ahead of you, now there is a new node ahead of you, so did not have to move. So you can just continue with if/else checks and sooner or later you will reach the end or you will drop the last node ahead of you.

One input example to illustrate this point is

head(1) -> 1 -> 1 -> 1 -> null

With such an input, the algorithm would only do

  • drop next
  • drop next
  • drop next

and it would be done.

No "go next" happened at all.

Result

head(1) -> null
user_24222240

Using solution 1 as a reference because the answer applies to both solutions. When you find a duplicate at the current node (head), you set the previous node’s (prev) next node to the current node’s next node (which removes the duplicate). On the next iteration, you will go to the next node in the list which is already being pointed at by the previous node. So, there is no need to overwrite prev. Another way to think about it is that the head you would be setting prev to is the node that you just removed. You wouldn’t want to do that.

Before removal: node1 (prev) -> node2(head) -> node3

After removal: node1 (prev) -> node3 (head)

As you can see, prev stays the same. No need to update it.

user_146343630

removeDuplicates:

If we remove a duplicate, the current removed node should not be assigned to prev. In fact prev is the previous node in the remaining kept list of uniques.

As is entirely evident, when there are more than 2 repeated values.

... -> prev: [42] -> [42] -> [42] -> [51] -> ...

should become

... -> prev: [42] -> [51] -> ...

removeDuplicatesTradeOff:

The same case. p2 (the previous node) may only advance when no duplicate was found.

Then there is a tiny bug:

removeDuplicates should return the new head normally - in case the head node is removed:

head = remove...(head); // Must assign, should the head node itself be removed.

Now it returns null. However for duplicates, the head node is never deleted. So either make it a void function or return the old head.

public static Node removeDuplicates(Node head){
    Node prev = null;
    Set<Integer> hs = new HashSet<>();

    Node current = head;
    // Loop-invariant: hs.isEmpty() || prev != null
    while (current != null) {
        if (hs.contains(current.data)) {
            prev.next = current.next;
        } else {
            hs.add(current.data);
            prev = current;
        }
        current = current.next;
    }
    return head;
}

Also notice that it is bad style using the name head for a running pointer.

user_9848230
Related