The question we are going to take a look at today is how to remove duplicates from a LinkedList. We’re going to be using PHP for the coding part, just because it’s the language I use more these days. Remember, languages don’t matter as much in this basic interview questions.
So first of all, since we’re doing this in PHP, let’s try to define a simple LinkedList API.
How To Remove Duplicates From a LinkedList in PHP – LinkedList API
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
public class ListNode { public $value; public $next = null; public function __construct($value) { $this->value = $value; } } public class LinkedList { public $head; public function __construct($head) { $this->head = $head; } } |
This is a very basic implementation to help us answer our question on how to remove duplicates from a LinkedList in PHP.
So let’s jump into thinking about our problem. As always the first thing we should do is ask for clarification on the requirements. When we try to remove duplicates from a LinkedList:
- Does removing duplicates means manipulating the current list?
- Should we remove duplicates so elements still stay, or should we remove all elements that are non unique?
- Are we concerned about any time / space bottlenecks?
- What’s the size of the list?
So let’s make some assumptions that we got answers for these three questions. We do need to manipulate the current list. We are only removing the dupes (i.e. 5->2->2->3 will result in 5->2->3 not 5->3) and we know the list is not going to be too big so are concerned with time.
Well if we were concerned with space we could have tried to come up with some in-place sorting algorithm that would save auxiliary space, but in this case, our algorithm to remove duplicates from a LinkedList should be as follows:
- Loop the LinkedList.
- Check elements against a temp hashtable. If element found, then it’s a dupe, if not found, insert it.
Sounds like a simple O(N) algorithm :). Let’s put our words into code!
How To Remove Duplicates From a LinkedList in PHP – Solution
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
public function removeDupes($linkedList) { $lastNode = $linkedList->head; $currNode = $lastNode->next; $tempCache = []; while ($currNode) { $val = $currNode->value; if (isset($tempCache[$val])) { $currNode = $currNode->next; $lastNode->next = $currNode; // Found a duplicate - point to the next node. } else { $lastNode = $currNode; $currNode = $currNode->next; $tempCache[$val] = true; } } return $linkedList; } |
That was about it! Wasn’t too hard! Well next time you get asked how to remove duplicates in a linkedlist in an interview I am sure you will ace it.
Hope you guys enjoyed it… and I’ll see you guys next time ;D
Latest posts by Ajk (see all)
- Find Median from Numbers Array - January 1, 2018
- Find Whether a Number Can Be the Sum of Two Squares - August 12, 2017
- How to Find Two Primes Whose Sum is Equal to a Number N - April 22, 2017