Union and Intersection of Linked Lists (Hashing)

Given two singly linked lists, build:

the union: the distinct values that appear in either list, in order of first appearance (list 1, then list 2)
the intersection: the distinct values that appear in both lists, in list 1's order

The inputs are only read.

This is the hashing version of Union and Intersection of Linked Lists.

Example

Text

list1: 10 -> 20 -> 80 -> 60
list2: 15 -> 20 -> 30 -> 60 -> 45

union:        10 -> 20 -> 80 -> 60 -> 15 -> 30 -> 45
intersection: 20 -> 60

Brute force: linear scans

Collect each list's values, then decide each candidate with contains, which scans a List. The result is built with a dummy node and a tail reference: the dummy node is a placeholder before the real head, so the first append needs no special case.

Linked structures in Java use null for "no next node" and mutable next fields, so no wrapper types are needed.

Java

import java.util.ArrayList;
import java.util.List;

public class Main {
    static class ListNode {
        int val;
        ListNode next;

        ListNode(int val) {
            this.val = val;
        }
    }

    static ListNode fromArray(int... values) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        for (int v : values) {
            tail.next = new ListNode(v);
            tail = tail.next;
        }
        return dummy.next;
    }

    static List<Integer> values(ListNode head) {
        List<Integer> out = new ArrayList<>();
        for (ListNode n = head; n != null; n = n.next) {
            out.add(n.val);
        }
        return out;
    }

    static ListNode build(List<Integer> values) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        for (int v : values) {
            tail.next = new ListNode(v);
            tail = tail.next;
        }
        return dummy.next;
    }

    static ListNode union(ListNode a, ListNode b) {
        List<Integer> out = new ArrayList<>();
        List<Integer> all = values(a);
        all.addAll(values(b));
        for (int v : all) {
            if (!out.contains(v)) out.add(v);
        }
        return build(out);
    }

    static ListNode intersection(ListNode a, ListNode b) {
        List<Integer> other = values(b);
        List<Integer> out = new ArrayList<>();
        for (int v : values(a)) {
            if (other.contains(v) && !out.contains(v)) out.add(v);
        }
        return build(out);
    }

    public static void main(String[] args) {
        ListNode a = fromArray(10, 20, 80, 60);
        ListNode b = fromArray(15, 20, 30, 60, 45);
        System.out.println(values(union(a, b)));
        System.out.println(values(intersection(a, b)));
    }
}

Output

[10, 20, 80, 60, 15, 30, 45]
[20, 60]

Time: O((n + m)²). Space: O(n + m).

Optimal: hash sets

Union: walk list 1 and then list 2. Keep a value when seen.add(v) returns true, which happens only the first time.
Intersection: load list 2's values into a set. Walk list 1 and keep a value when inB.remove(v) returns true. Removing it prevents a repeated value in list 1 from being added twice.

Walkthrough for the union:

value	source	`seen.add`	kept?
10, 20, 80, 60	list 1	true each time	yes
15	list 2	true	yes
20	list 2	false	no
30	list 2	true	yes
60	list 2	false	no
45	list 2	true	yes

Java

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Main {
    static class ListNode {
        int val;
        ListNode next;

        ListNode(int val) {
            this.val = val;
        }
    }

    static ListNode fromArray(int... values) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        for (int v : values) {
            tail.next = new ListNode(v);
            tail = tail.next;
        }
        return dummy.next;
    }

    static List<Integer> values(ListNode head) {
        List<Integer> out = new ArrayList<>();
        for (ListNode n = head; n != null; n = n.next) {
            out.add(n.val);
        }
        return out;
    }

    static ListNode build(List<Integer> values) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        for (int v : values) {
            tail.next = new ListNode(v);
            tail = tail.next;
        }
        return dummy.next;
    }

    static ListNode union(ListNode a, ListNode b) {
        Set<Integer> seen = new HashSet<>();
        List<Integer> out = new ArrayList<>();
        for (ListNode list : new ListNode[]{a, b}) {
            for (ListNode n = list; n != null; n = n.next) {
                if (seen.add(n.val)) out.add(n.val);
            }
        }
        return build(out);
    }

    static ListNode intersection(ListNode a, ListNode b) {
        Set<Integer> inB = new HashSet<>(values(b));
        List<Integer> out = new ArrayList<>();
        for (ListNode n = a; n != null; n = n.next) {
            if (inB.remove(n.val)) out.add(n.val);
        }
        return build(out);
    }

    public static void main(String[] args) {
        ListNode a = fromArray(10, 20, 80, 60);
        ListNode b = fromArray(15, 20, 30, 60, 45);
        System.out.println(values(union(a, b)));
        System.out.println(values(intersection(a, b)));
        System.out.println(values(intersection(fromArray(1, 1, 2), fromArray(1, 2, 2))));
    }
}

Output

[10, 20, 80, 60, 15, 30, 45]
[20, 60]
[1, 2]

Time: O(n + m). Space: O(n + m).

Both functions only read their inputs and build new nodes, so the original lists can still be used after the call.