Remove Duplicates from a Linked Lists

Algo Expert — Easy

I am going to focus on Linked Lists this week. To better prepare me for future interviews. I started today with this problem.

Problem:

You are given the head of a Singly Linked List whose nodes are sorted in order with respect to their values. Write a function that returns a modified version of the linked lists that doesn't contain any nodes with duplicate values.

Example:

input: 1 -> 1 -> 3 -> 4 -> 4-> 4-> 5-> 6

output: 1-> 3->4 ->5 ->6

Solution:

With a Linked List we have a head = first node we also have a class with two attributes this.value = value and this.next = null. (next node or null (if its null it means that is the last node in the list).

In order for us to check for duplicates, we will need to start at the head and check the current node with the next node. if they match then we need to move the pointer to the following node. Once we find a value that is different then we change the current node to that value and the next node to the one next to it and proceed until we get to the end of the list.

Below is the code solution. O(n) time and O(1) space

class LinkedList {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}
function removeDuplicatesFromLinkedList(linkedList) {
  let currentNode = linkedList
	while (currentNode !== null) {
		let nextDistinctNode = currentNode.next
		while (nextDistinctNode !== null && nextDistinctNode.value === currentNode.value) {
		    nextDistinctNode = nextDistinctNode.next
		}
		currentNode.next = nextDistinctNode
		currentNode = nextDistinctNode
	}
  return linkedList;
}

As you can see we have the class with the constructor.
Then we proceed with the function in which we pass in the linkedList which is the head. And then the head is saved in the current node variable.

While the currentNode is not null we will continue to iterate through. Then we save currentNode.next in nextDistinctNode variable. And while the nextDisctinctNode is not null and it is the same as the current node (meaning it is DUPLICATED) then we will continue to move on to the next node and save that in the nextDistinctNode variable.
Once the while loop is finished which means we found the value that is distinct and is not the same as the current value then we want to remove all of the other nodes. Therefore we do currentNode.next = nextDistinctNode (This is where we get rid of that duplicate value and move the pointer to the new value.) and then we change our currentNode = nextDisctinctNode

Bringing us to the end to return the linkedList. Keep in mind that this solution works this way because we were provided with a sorted Linked List.