## Table of Contents

Given a sorted linked list, write a function to remove all the duplicate elements from the list, such that each element appears only once.

Example:

Input: 1 -> 1 -> 2 Output: 1 -> 2

Input: 1 -> 1 -> 2 -> 3 -> 3 Output: 1 -> 2 -> 3

Solution:

One approach to solve this problem is to traverse the linked list and keep track of the previous node and the current node. If the data of the previous node and the current node are the same, then we can remove the current node by skipping it.

## Solution in Java:

While Java does have a built-in `LinkedList`

class, it’s a good idea to understand how linked lists work and implement your own class. This can help you gain a better understanding of the data structure and make it easier to solve problems during an interview.

When implementing your own linked list class in Java, you’ll need to define a `Node`

class to represent each node in the list. The `Node`

class should have a `value`

field to store the data and a `next`

field to store a reference to the next node in the list.

You can then define a `LinkedList`

class that has a `head`

field to store a reference to the first node in the list. The `LinkedList`

class should have methods to add and remove nodes from the list, as well as to traverse the list and perform any necessary operations.

```
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public ListNode deleteDuplicates(ListNode head) {
ListNode curr = head;
while (curr != null && curr.next != null) {
if (curr.val == curr.next.val) {
curr.next = curr.next.next;
} else {
curr = curr.next;
}
}
return head;
}
```

## Solution in Ruby:

In Ruby, there is a built-in `LinkedList`

class that you can use to implement a linked list. However, it’s important to understand how linked lists work and how to implement them yourself without relying on libraries. This will give you a better understanding of the underlying data structure and help you to write more efficient code.

```
class ListNode
attr_accessor :val, :next
def initialize(val = 0, _next = nil)
@val = val
@next = _next
end
end
def delete_duplicates(head)
curr = head
while curr && curr.next
if curr.val == curr.next.val
curr.next = curr.next.next
else
curr = curr.next
end
end
head
end
```

## Solution in Python:

```
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def delete_duplicates(head: ListNode) -> ListNode:
curr = head
while curr and curr.next:
if curr.val == curr.next.val:
curr.next = curr.next.next
else:
curr = curr.next
return head
```

## Solution in JavaScript:

```
function ListNode(val) {
this.val = val;
this.next = null;
}
var deleteDuplicates = function(head) {
var curr = head;
while (curr !== null && curr.next !== null) {
if (curr.val === curr.next.val) {
curr.next = curr.next.next;
} else {
curr = curr.next;
}
}
return head;
};
```

In each of the solutions above, we define a `ListNode`

class to represent each node in the linked list. We then define a function called `deleteDuplicates`

which takes the head of the linked list as input.

The function then iterates through the linked list using a while loop, keeping track of the current node (`curr`

) and its next node. If the data of the current node and its next node are the same, we skip the next node by setting the `next`

pointer of the current node to point to the node after the next node. Otherwise, we move on to the next node.

The time complexity of the above solution is O(n) where n is the number of nodes in the linked list. This is because we only need to traverse the linked list once, and each operation inside the loop is constant time.

An alternative solution to remove duplicates from a sorted linked list is to use a hash set to keep track of the values we have already seen. We can then iterate through the linked list and remove any nodes whose values are already in the hash set.

## Pseudocode for the alternative solution:

```
function removeDuplicates(head):
if head is null:
return null
seen = new set()
curr = head
prev = null
while curr is not null:
if curr.val in seen:
prev.next = curr.next
else:
seen.add(curr.val)
prev = curr
curr = curr.next
return head
```

In the code above, we first check if the linked list is empty and return `null`

if it is. We then create an empty hash set called `seen`

and initialize the current node `curr`

to the head of the linked list and the previous node `prev`

to `null`

.

We then loop through the linked list using a while loop, checking if the value of the current node is already in the `seen`

hash set. If it is, we skip the current node by setting the `next`

pointer of the previous node to the node after the current node. Otherwise, we add the value of the current node to the `seen`

hash set and set `prev`

to `curr`

. We then move on to the next node by setting `curr`

to `curr.next`

.

Finally, we return the head of the linked list which now contains only unique elements.

The time complexity of this solution is also O(n) where n is the number of nodes in the linked list, but it requires additional memory to store the hash set. However, it can be more efficient if the linked list is not sorted or if duplicates are more common, as the previous solution would require iterating through the entire list to remove duplicates.