Merge two sorted lists into a duplicate-free union

Question

You are given the heads of two singly linked lists, each sorted ascending and each possibly containing repeats. Merge them into one ascending list in which every value appears exactly once, relinking existing nodes rather than copying payloads, and return the new head.

l1: 1 -> 2 -> 2 -> 4
l2: 2 -> 3 -> 4
->  1 -> 2 -> 3 -> 4

Target $O(m + n)$ time and $O(1)$ extra space.

Accepted Answer

Run the ordinary two-pointer merge, but before attaching a node, check whether its value equals the value already at the tail; if so, skip it. Since the inputs are sorted, all copies of a value arrive consecutively in the merged order, so this single tail-check removes both within-list and cross-list duplicates. Tracing the example: 1 attaches; 2 attaches; the second l1 2 is skipped (matches the tail); 3 attaches; the two 4s collapse to one. Result 1 - 2 - 3 - 4. Comparing against tail.is dummy avoids a false match when a real value happens to equal the dummy's 0; the closing tail.next = None…

Merge two sorted lists into a duplicate-free union

Your answer

More Coding questions