Union and Intersection of Linked Lists

Given two singly linked lists, build two new lists:

the union: every distinct value that appears in either list
the intersection: every distinct value that appears in both lists

Values appear in the order they're first seen: for the union, list 1 first and then list 2. For the intersection, the order of list 1. The input lists are only read, not changed.

Example

Text

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

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

graph LR
    subgraph l1["list 1"]
        a1["10"] --> a2["20"] --> a3["80"] --> a4["60"]
    end
    subgraph l2["list 2"]
        b1["15"] --> b2["20"] --> b3["30"] --> b4["60"] --> b5["45"]
    end

20 and 60 are in both lists, so they're the intersection.

Brute force: scan the lists

For every candidate value, scan a list to answer "is this value already there?":

Union: for each value in list 1 and then list 2, add it if the result doesn't contain it yet.
Intersection: for each value in list 1, add it if list 2 contains it and the result doesn't yet.

A list node here is an object with a mutable next field, and null marks the end of the list. The result is built with a dummy node and a tail pointer. tail always points at the last node of the result, so appending is O(1). The dummy node means the first append needs no special case, and dummy.next is the result head.

Java

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

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

    static boolean contains(ListNode list, int val) {
        for (ListNode n = list; n != null; n = n.next) {
            if (n.val == val) return true;
        }
        return false;
    }

    static ListNode union(ListNode a, ListNode b) {
        ListNode dummy = new ListNode(0, null);
        ListNode tail = dummy;
        for (ListNode list : new ListNode[]{a, b}) {
            for (ListNode n = list; n != null; n = n.next) {
                if (!contains(dummy.next, n.val)) {
                    tail.next = new ListNode(n.val, null);
                    tail = tail.next;
                }
            }
        }
        return dummy.next;
    }

    static ListNode intersection(ListNode a, ListNode b) {
        ListNode dummy = new ListNode(0, null);
        ListNode tail = dummy;
        for (ListNode n = a; n != null; n = n.next) {
            if (contains(b, n.val) && !contains(dummy.next, n.val)) {
                tail.next = new ListNode(n.val, null);
                tail = tail.next;
            }
        }
        return dummy.next;
    }

    static ListNode fromArray(int... values) {
        ListNode head = null;
        for (int i = values.length - 1; i >= 0; i--) {
            head = new ListNode(values[i], head);
        }
        return head;
    }

    static String show(ListNode list) {
        StringBuilder sb = new StringBuilder("[");
        for (ListNode n = list; n != null; n = n.next) {
            if (n != list) sb.append(", ");
            sb.append(n.val);
        }
        return sb.append("]").toString();
    }

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

Output

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

Time: O((n + m)²): each of the n + m values scans a list of up to n + m nodes. Space: O(1) besides the output.

Optimal: hash sets

A HashSet answers "have I seen this value?" in O(1) expected time.

Union: walk list 1 and then list 2. Append a value when seen.add(v) returns true, which means it's the first time the value has been seen.
Intersection: put all of list 2's values into a set. Walk list 1 and append a value when inB.remove(v) returns true. Removing it means that if the value appears again in list 1, it won't be added twice.

The result is still built with the dummy node and tail, so the output order follows the walk order, not the set order. The sets are only used for membership tests, so their unspecified iteration order does not matter.

Walkthrough for the intersection. inB starts as {15, 20, 30, 60, 45}:

list 1 value	`inB.remove(v)`	appended?	`inB` after
10	false	no	{15, 20, 30, 60, 45}
20	true	yes	{15, 30, 60, 45}
80	false	no	{15, 30, 60, 45}
60	true	yes	{15, 30, 45}

Java

import java.util.HashSet;
import java.util.Set;

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

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

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

    static ListNode intersection(ListNode a, ListNode b) {
        Set<Integer> inB = new HashSet<>();
        for (ListNode n = b; n != null; n = n.next) inB.add(n.val);
        ListNode dummy = new ListNode(0, null);
        ListNode tail = dummy;
        for (ListNode n = a; n != null; n = n.next) {
            if (inB.remove(n.val)) {
                tail.next = new ListNode(n.val, null);
                tail = tail.next;
            }
        }
        return dummy.next;
    }

    static ListNode fromArray(int... values) {
        ListNode head = null;
        for (int i = values.length - 1; i >= 0; i--) {
            head = new ListNode(values[i], head);
        }
        return head;
    }

    static String show(ListNode list) {
        StringBuilder sb = new StringBuilder("[");
        for (ListNode n = list; n != null; n = n.next) {
            if (n != list) sb.append(", ");
            sb.append(n.val);
        }
        return sb.append("]").toString();
    }

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

Output

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

Time: O(n + m) on average. Space: O(n + m) for the sets and the output.

Set<Integer> stores boxed Integer objects, and remove(n.val) boxes the int automatically. HashSet compares values with equals, so equal numbers match even when they are different Integer objects.

Edge cases

One list empty: the union is the other list without duplicates, and the intersection is empty.
Duplicates inside one list: they appear once in each result.
No common values: the intersection is empty.