Overview
Detecting and removing duplicates from an unsorted linked list is a common problem in linked list interview questions. It tests the candidate's understanding of data structures, particularly linked lists, and their ability to manipulate them. Removing duplicates is crucial for maintaining a set of unique elements in a list, which is often a prerequisite for other algorithms.
Key Concepts
- Traversal: Efficiently navigating through each element of a linked list.
- Hashing: Using a data structure like a HashSet to track already seen elements.
- Two-Pointer Technique: An approach for in-place removal of duplicates without extra space.
Common Interview Questions
Basic Level
- How do you traverse a linked list to print all its elements?
- Implement a function to append a node to a linked list.
Intermediate Level
- How can you remove duplicates from an unsorted linked list using extra space?
Advanced Level
- Can you remove duplicates from an unsorted linked list without using extra space?
Detailed Answers
1. How do you traverse a linked list to print all its elements?
Answer: Traversing a linked list involves starting from the head node and moving through each node until the end of the list (null) is reached. During traversal, we print the value of each node.
Key Points:
- Use a temporary pointer starting at the head.
- Loop until the pointer is null.
- Move the pointer to the next node after printing its value.
Example:
public class ListNode
{
public int Value;
public ListNode Next;
public ListNode(int value)
{
this.Value = value;
this.Next = null;
}
}
public void PrintLinkedList(ListNode head)
{
ListNode current = head;
while (current != null)
{
Console.WriteLine(current.Value);
current = current.Next;
}
}
2. Implement a function to append a node to a linked list.
Answer: Appending a node involves traversing to the end of the list and setting the next pointer of the last node to a new node.
Key Points:
- If the list is empty, the new node becomes the head.
- Otherwise, traverse to the last node.
- Set the next pointer of the last node to the new node.
Example:
public void AppendNode(ListNode head, int newValue)
{
ListNode newNode = new ListNode(newValue);
if (head == null)
{
head = newNode;
return;
}
ListNode current = head;
while (current.Next != null)
{
current = current.Next;
}
current.Next = newNode;
}
3. How can you remove duplicates from an unsorted linked list using extra space?
Answer: Using a HashSet to track visited values, we can remove duplicates by iterating through the list and only keeping nodes with unique values.
Key Points:
- Initialize a HashSet to keep track of values.
- Use two pointers: previous and current. Previous stays behind current.
- If current's value is in HashSet, remove it by setting previous's next to current's next.
- If not, add the value to HashSet and move previous to current.
Example:
public void RemoveDuplicates(ListNode head)
{
HashSet<int> seen = new HashSet<int>();
ListNode current = head;
ListNode prev = null;
while (current != null)
{
if (seen.Contains(current.Value))
{
prev.Next = current.Next; // Skip current node
}
else
{
seen.Add(current.Value);
prev = current; // Move prev to current
}
current = current.Next; // Move to next node
}
}
4. Can you remove duplicates from an unsorted linked list without using extra space?
Answer: This can be achieved by using the two-pointer technique, where for each node, we iterate through the remainder of the list, removing nodes with the same value.
Key Points:
- Use two loops: the outer loop selects a node, and the inner loop compares it against the rest.
- If a duplicate is found, remove it by adjusting pointers.
- This method has O(n^2) time complexity but does not use extra space.
Example:
public void RemoveDuplicatesWithoutSpace(ListNode head)
{
ListNode current = head;
while (current != null)
{
ListNode runner = current;
while (runner.Next != null)
{
if (runner.Next.Value == current.Value)
{
runner.Next = runner.Next.Next; // Remove duplicate
}
else
{
runner = runner.Next; // Move to next
}
}
current = current.Next; // Move to next node
}
}
This guide covers detecting and removing duplicates from an unsorted linked list, including both space-efficient and in-place methods, providing a comprehensive understanding for advanced linked list interview questions.
