[FIXED] Remove Duplicates from Linked List

Issue

So I have a linked list that I am trying to remove duplicates from.

My basic algorithm that I thought up is to pretty much use the runner technique. Where I keep two pointers to compare adjacent elements. If they are the same I change the pointer of p1 to point to p1.next.next if not I keep traversing the list. However I keep getting a null pointer exception in the solution I have typed.

Node RemoveDuplicates(Node head) {
  // This is a "method-only" submission. 
  // You only need to complete this method. 
    if (head == null){
        return null;
    } 

        Node current = head;
    Node runner = head;



    while(current != null && runner != null && runner.next != null){
    runner = runner.next;
    if(runner.data == current.data){
        if(current.next != null){
                    current = current.next.next; 

        }
    }else{
        current = current.next;
    }
}



    return current;
}

At the point that I exit the while loop current is null. Which I think is the problem. How would I return the head of the altered list.

Solution

First of all, you'll want to return head at the end, so that you are returning the list, not just the last element. Second thing, you'll want to modify the .next references instead of assigning them in some of the cases.

Note this doesn't work if the list isn't sorted.

Before: 1 1 3 3
After: 1 3

This code works (and I've tested it)

static Node RemoveDuplicates(Node head) {
    if (head == null) return null;

    Node current = head;
    Node runner = head;

    while (current != null && current.next != null) {
        runner = current.next;
        while (runner != null && runner.data == current.data) {
            current.next = runner.next; // skip the repeat
            runner = runner.next;
        }
        current = current.next;
    }
    return head;
}

Answered By - Zach Jones
Answer Checked By - Cary Denson (JavaFixing Admin)