Remove duplicates from a sorted linked list.

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.