Deduplicate a Linked List

Q: Deduplicate a Linked List

This question evaluates proficiency in linked list manipulation, in-place data structure modification, and reasoning about time-space trade-offs for removing duplicate elements.

Q: How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

Q: What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Salesforce.

Q: What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Salesforce during technical interviews.

Question

Given a singly linked list, remove duplicate values in-place. Variant A (sorted list): delete repeated nodes so each value appears once using O(
1) extra space. Variant B (unsorted list): delete duplicates while preserving the first occurrence; provide two solutions—
(
1) using a hash set and
(
2) without extra memory using the runner technique. Define your ListNode type, explain correctness, analyze time and space complexity for each approach, and include tests for edge cases (empty list, single node, all duplicates, no duplicates).

PracHub · Accepted Answer

def solution(values):
    class ListNode:
        __slots__ = ('val', 'next')

def __init__(self, val=0, next=None):
            self.val = val
            self.next = next

def build_linked_list(vals):
        dummy = ListNode()
        tail = dummy
        for v in vals:
            tail.next = ListNode(v)
            tail = tail.next
        return dummy.next

def to_list(head):
        result = []
        while head is not None:
            result.append(head.val)
            head = head.next
        return result

head = build_linked_list(values)

current = head
    while current is not None and current.next is not None:
        if current.val == current.next.val:
            current.next = current.next.next
        else:
            current = current.next

return to_list(head)

def solution(values, method='hash'):
    class ListNode:
        __slots__ = ('val', 'next')

def __init__(self, val=0, next=None):
            self.val = val
            self.next = next

def build_linked_list(vals):
        dummy = ListNode()
        tail = dummy
        for v in vals:
            tail.next = ListNode(v)
            tail = tail.next
        return dummy.next

def to_list(head):
        result = []
        while head is not None:
            result.append(head.val)
            head = head.next
        return result

head = build_linked_list(values)

if method == 'hash':
        if head is None:
            return []

seen = {head.val}
        current = head
        while current.next is not None:
            if current.next.val in seen:
                current.next = current.next.next
            else:
                seen.add(current.next.val)
                current = current.next

elif method == 'runner':
        current = head
        while current is not None:
            runner = current
            while runner.next is not None:
                if runner.next.val == current.val:
                    runner.next = runner.next.next
                else:
                    runner = runner.next
            current = current.next

else:
        raise ValueError("method must be either 'hash' or 'runner'")

return to_list(head)

Quick Overview

Hints

Part 2: Deduplicate an Unsorted Singly Linked List While Preserving First Occurrences

Constraints

Examples

Solution

Hints

Quick Overview