Problem

Write code to remove duplicates from an unsorted linked list.

FOLLOW UP: How would you solve this problem if a temporary buffer is not allowed?

Examples

Example 1:

2 -> 3 -> 2 -> 5 -> 2 -> 8 -> 2 -> 3 -> 8 -> null
=>
2 -> 3 -> 5 -> 8 -> null

Input: head = [2, 3, 2, 5, 2, 8, 2, 3, 8]
Output: [2, 3, 5, 8]

We have already seen Remove duplicates from Sorted List 1. Now we will see deleting from the unsorted list.

Follow up

Remove duplicates from an unsorted linked list keeping only unique elements

Solutions

Method 1 - Using Two Loops

This approach uses two loops: the outer loop selects each element one by one, while the inner loop compares the selected element with the remaining elements. The algorithm uses two pointers called current and runner. Current iterates through the list normally, whereas runner checks previous nodes for duplicates as it progresses. The runner pointer ensures that only one duplicate is encountered at a time.

Code

Java
public class Solution {

	public ListNode deleteDuplicates(ListNode head) {
		if (head == null) {
			return null;
		}

		ListNode current = head;

		// Iterate through the list
		while (current != null) {
			ListNode runner = current;
			// Remove all future nodes that have the same value as the current node
			while (runner.next != null) {
				if (runner.next.val == current.val) {
					runner.next = runner.next.next; // Remove the duplicate node
				} else {
					runner = runner.next; // Move to next node
				}
			}

			current = current.next;
		}

		return head;
	}
}

Complexity

  • ⏰ Time complexity: O(n^2)
  • 🧺 Space complexity: O(1)

Method 2 - Use Sorting

  1. Sort the linked list, that takes O(n log n) time. See more - Sort a Linked List
  2. Remove duplicates in linear time using the Remove duplicates from Sorted List 1, and that takes O(n)

Please note that this method doesn’t preserve the original order of elements.

Complexity

  • ⏰ Time complexity: O(n log n)
  • 🧺 Space complexity: O(1)

Method 3 - Use Hashing

We following steps:

  1. We traverse the linked list from the head to the end.
  2. For each new element, we check if it is in the hash table: if it is, we remove it; otherwise, we add it to the hash table.

Follow up question’s solution is method 1, as we don’t want to use any extra space.

Code

Java
public class Solution {

	public ListNode deleteDuplicates(ListNode head) {
		if (head == null) {
			return null;
		}

		Set<Integer> seen = new HashSet<>();
		ListNode current = head;
		ListNode prev = null;

		while (current != null) {
			if (seen.contains(current.val)) {
				// Duplicate node, remove it
				prev.next = current.next;
			} else {
				// Not a duplicate, add to the set
				seen.add(current.val);
				prev = current;
			}

			current = current.next;
		}

		return head;
	}
}

Complexity

  • ⏰ Time complexity: O(n) as we loop on elements, and it takes O(1) time to add and read the value in hashset.
  • 🧺 Space complexity: O(n) for storing the values in hashset.