Removing duplicated nodes from sorted linked list. Why is my output wrong?

Question

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

Examples:

• Given 1->2->3->3->4->4->5->null, return 1->2->5->null.

• Given 1->1->1->2->3->null, return 2->3->null.

Problem:

• Given 1->1->1->2->3->null, my solution below return 3->null

Can someone tell me why?

/**
 * Definition for ListNode
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param ListNode head is the head of the linked list
     * @return: ListNode head of the linked list
     */
    public static ListNode deleteDuplicates(ListNode head) {
        // write your code here
        if(head == null || head.next == null) return head;

        ListNode post = head.next;
        ListNode curr = head;
        ListNode dummy = new ListNode(head.val-1);  // make sure dummy node value is different from the head
        dummy.next = head;
        ListNode prev = dummy;

        while(post != null) {
            //System.out.println("prev.val = " + prev.val + ", curr.val = " + curr.val + ", post.val = " + post.val + ", prev.next.val = " + prev.next.val);   
            //System.out.println("prev.next.val = " + prev.next.val + ", curr.next.val = " + curr.next.val);            

            if(prev.next.val == curr.val && prev.next.val == post.val) {
                curr = curr.next;
                post = post.next;
            }
            else if(prev.next.val == curr.val && prev.next.val != post.val) {
                curr = curr.next;
                post = post.next;                
                prev.next = curr;
            }
            else {
                prev = prev.next;
                curr = curr.next;
                post = post.next;
            }
        }

        return dummy.next;
    }
}

Answer 1

public static ListNode deleteDuplicates(ListNode head) {

    // do nothing if the list is empty
    if (head == null) {
        return null;
    }

    ListNode current = head;

    // compare the current node with the next node
    while (current.next != null) {
        if (current.data == current.next.data)
            current.next = current.next.next;
        else
            current = current.next;    // only advance if no deletion
    }
    return head;
}

Answer 2

Without changing what your program does, the while loop can be transformed to this more readable form:

while (post != null) {
    if (prev.next.val != curr.val || prev.next.val != post.val) {
        if (prev.next.val == curr.val) {
            prev.next = curr.next;
        } else {
            prev = prev.next;
        }
    }
    curr = curr.next;
    post = post.next;
}

This is equivalent to your actual code. I will explain based on this version, because I find this easier to read and reason about.

Let's observe a few things:

• In the beginning, prev.next points at curr. So prev.next.val is equal to curr.val. Also, post is one step ahead of curr.

• curr moves together with post. curr and post are not changed inside the if condition, and as the last step of the loop, they both advance by one position forward.

Given the input 1, 1, 1, 2, 3, and the above observations:

• The outer if condition will be false until post reaches 2.

• curr is one step behind, so it points to the 1 that's right before 2.

• prev did not move, so prev.next still points to the first 1.

• So at this point, prev.next.val is equal to curr.val (both 1), but it's not equal to post.val, which is 2. So we enter the outer if.

• As prev.next.val == curr.val, we also enter the inner if, and set prev.next = curr.next. Remember that the last step of the loop will be advancing curr to curr.next. So prev.next will be pointing at curr.

• In the next iteration, we have post at 3, and curr at 2, and prev.next pointing at curr. So we enter the other if, and then the inner if, setting prev.next to curr.next, which is 3.

And this is the end. prev never moved, it stayed where it was, which is dummy. prev.next is pointing at 3, which we return, incorrectly. Note that if the input was longer, for example 1, 1, 1, 2, 3, 4, 5, 6, the same behavior will continue, prev.next following curr, and the implementation would incorrectly return 6 -> null. The algorithm is broken.

---

Consider this alternative algorithm:

1. Create a dummy node, pointing to head as next (as you already did)
2. Set the current node to dummy
3. While the next node exists, and the next-next node exists
   • Compare next.val and next.next.val
   • If not equal, then advance the current node
   • If equal, then:
     • Save a copy of next.val
     • Skip next and next.next (set next to next.next.next)
     • Skip all further nodes whose value is equal to the saved val
4. Return dummy.next

Like this:

if (head == null) return head;

ListNode dummy = new ListNode(head.val - 1);
dummy.next = head;

ListNode node = dummy;
while (node.next != null && node.next.next != null) {
    if (node.next.val != node.next.next.val) {
        node = node.next;
    } else {
        int val = node.next.val;
        node.next = node.next.next.next;
        while (node.next != null && node.next.val == val) {
            node.next = node.next.next;
        }
    }
}

return dummy.next;