I was doing a problem on LeetCode the other day that had the following problem:
Given a sorted linked list, delete all duplicates such that each element appear only once.
An example input gave the following:
Input: 1->1->2->3->3 Output: 1->2->3
Channeling Dave Chapelle like my last Linked List post, my mind went like…
But thanks to the wonders of the internet, all this information of what linked lists are and how to handle them is at my fingertips
A refresher on the structure of linked lists
In my last post about linked lists, I described them as a linear data structure that is a little bit different from arrays. If you recall, here’s a visual representation of a linked list.
If this data structure were an array and I wanted to get to C, it’d be pretty simple by just typing arr[2] and that’s it. However, linked lists do not allow random access. If you want to get to element C in a linked list, you’ll have to start at the head and make your way down.
Traversing the Linked list
Recall what the constructor of a node in a list looks like:
class Node {
// constructor
constructor(element)
{
this.element = element;
this.next = null
}
}
and that the code for a linked list, which holds the head of the list, and the size, or number of nodes, of the list
// linkedlist class
class LinkedList {
constructor()
{
this.head = null;
this.size = 0;
}
}
A simple traversal without doing much would look something like this:
//traversal code snippet
let current = this.head; //this assumes that a snippet like this would be within a function that's in the LinkedList class
while(current != null){
// do what you need to do here assuming the function that this loop is in does more
current = current.next
}
In the snippet above, we have a variable, current, that is equal to the LinkedList’s head. The head variable could be null, or it could point to a node object. Once it enters the while loop, it’ll check if current is null or not, and assuming that it’s not, it’ll set current to the next node that current is pointing to.
You’ll know that you’re at the tail of a list if the last node on a list points to nothing as its next element. Once we’re at the tail, the loop will terminate.
Now about that LeetCode problem
Now, back to the LeetCode problem. Recall that we’re trying to remove duplicates. We know the limitations of a linked list. We don’t have random access capabilities like an array. What do we do?
The problem supplies us with the following starter code:
var deleteDuplicates = function(head) {
};
The function, deleteDuplicates, takes in a head argument. And that’s about it. So what next?
let node = head
if(node){
// what's next...
while(node.next !== null){
if(node.val === node.next.val)
node.next = node.next.next
else
node = node.next
}
}
return head
First, lets set head to a variable node and check to see if it’s null. There may be cases where we’ll get a null head and nothings actually in this list. We can simply do that by checking for truthiness for null. Recall that a null value is considered falsy.
let node = head
if(node){
while(node.next !== null){
if(node.val === node.next.val)
node.next = node.next.next
else
node = node.next
}
}
return head
Much like in the example in the section above, we need to use a while loop to do some traversal. We don’t really know how big this linked list unless we have access to the actual linked list object that holds the head and count value. A for loop is not a great iterator in this case.
Since this problem indicates that the list is already sorted (how fortunate!), we just need to do a few things:
- If the value of the current node, let’s call it NC, that we’re traversing though is equal to the value of the node that the current node is pointing to (node.next, or NN), then we have the current node’s next value point to not the next node, but the node after the next. In the next iteration of the loop, well evaluate the value of the current node to the new node that it’s pointing to.
- Otherwise, have current be the next node
We’ll keep doing until the node.next value is null, meaning we’re at the end.