Problem statement

You are given the heads of two linked lists, head1 and head2. Neither list is sorted, and a value may appear several times in either.

Return the head of a new linked list holding the union of the two lists: every value that appears in at least one of them, each value exactly once, in ascending order.

Example 1

Input: head1 = [9,6,4,2,3,8], head2 = [1,2,8,6,2]
Output: [1,2,3,4,6,8,9]
Explanation: The distinct values of both lists together, sorted.

Example 2

Input: head1 = [5,5,5], head2 = [5]
Output: [5]
Explanation: Duplicates within and across the lists collapse to one node.

Example 3

Input: head1 = [7,3], head2 = [10,1]
Output: [1,3,7,10]
Explanation: The lists share nothing, so all four values appear.

Constraints

• 1 <= number of nodes in each list <= 10^4
• 1 <= Node.val <= 10^4

Hints for Union of Two Linked Lists

1. Hint 1

   The output is fully determined by the set of values present — the order and repetitions in the inputs do not matter.

2. Hint 2

   Collect the values of both lists into a set (or a sorted set) to remove duplicates.

3. Hint 3

   Sort the distinct values and build a fresh list from them — or, with values bounded by 10^4, mark them in a boolean array and read it in increasing order.

How to solve Union of Two Linked Lists

The union is just the set of distinct values, so gather them, sort them, and turn the sorted values into a list.

Approach

1. Walk both lists, adding every value to a hash set.
2. Sort the set's values in ascending order.
3. Build a new linked list from the sorted values (append behind a dummy head) and return it.

Why it works

A value is in the union exactly when it occurs in one of the lists, which is exactly when it is in the set; the set holds each value once, and sorting fixes the required order.

Complexity

• Time — O((n + m) + u log u) — u distinct values
• Space — O(u)

Pitfalls

• Merging the lists first and removing adjacent duplicates only works after sorting — the inputs are unsorted.
• A value repeated inside a single list must still appear once.

Reference solution

Python

from typing import Optional

def makeUnion(head1: Optional[ListNode], head2: Optional[ListNode]) -> Optional[ListNode]:
    seen = set()
    for h in (head1, head2):
        while h:
            seen.add(h.val)
            h = h.next
    dummy = ListNode(0)
    tail = dummy
    for v in sorted(seen):
        tail.next = ListNode(v)
        tail = tail.next
    return dummy.next

Java

public static ListNode makeUnion(ListNode head1, ListNode head2) {
    TreeSet<Integer> seen = new TreeSet<>();
    for (ListNode h = head1; h != null; h = h.next) seen.add(h.val);
    for (ListNode h = head2; h != null; h = h.next) seen.add(h.val);
    ListNode dummy = new ListNode(0), tail = dummy;
    for (int v : seen) { tail.next = new ListNode(v); tail = tail.next; }
    return dummy.next;
}

C++

ListNode* makeUnion(ListNode* head1, ListNode* head2) {
    set<int> seen;
    for (ListNode* h = head1; h; h = h->next) seen.insert(h->val);
    for (ListNode* h = head2; h; h = h->next) seen.insert(h->val);
    ListNode dummy(0);
    ListNode* tail = &dummy;
    for (int v : seen) { tail->next = new ListNode(v); tail = tail->next; }
    return dummy.next;
}

JavaScript

var makeUnion = function(head1, head2) {
    var seen = new Set(), heads = [head1, head2];
    for (var i = 0; i < 2; i++) for (var h = heads[i]; h !== null; h = h.next) seen.add(h.val);
    var vals = Array.from(seen).sort(function (a, b) { return a - b; });
    var dummy = new ListNode(0), tail = dummy;
    for (var j = 0; j < vals.length; j++) { tail.next = new ListNode(vals[j]); tail = tail.next; }
    return dummy.next;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More hash table problems

• Implement Router Medium
• Design Task Manager Medium
• Frequency Tracker Medium
• Find Consecutive Integers from a Data Stream Medium
• Design Memory Allocator Medium
• Longest Uploaded Prefix Medium