Problem statement

You are given the heads of two singly linked lists, head1 and head2, each sorted in non-decreasing order. Build and return a new sorted linked list holding the values the two lists have in common; the input lists must not be changed.

Values may repeat. A value that appears a times in the first list and b times in the second appears min(a, b) times in the result. If the lists share nothing, return the empty list.

Example 1

Input: head1 = [1,2,3,4,6], head2 = [2,4,6,8]
Output: [2,4,6]

Example 2

Input: head1 = [10,20,40,50], head2 = [15,40]
Output: [40]

Example 3

Input: head1 = [1,1,2,2,2,5], head2 = [1,2,2,3]
Output: [1,2,2]
Explanation: 1 is shared once and 2 twice — as often as the list with fewer copies holds it.

Constraints

• 1 <= number of nodes in each list <= 10^4
• 1 <= Node.val <= 10^4
• Both lists are sorted in non-decreasing order

Hints for Intersection of Two Sorted Linked Lists

1. Hint 1

   Both lists are sorted — think of how merge sort walks two sorted sequences side by side.

2. Hint 2

   Compare the two current values: the smaller one cannot appear in the other list from here on, so skip it.

3. Hint 3

   When the values are equal, append a new node with that value to the result and advance both lists.

How to solve Intersection of Two Sorted Linked Lists

Walk both sorted lists with one pointer each, exactly like the merge step of merge sort, but keep a value only when both pointers show it — then move both on, which pairs copies one to one.

Approach

1. Set p = head1, q = head2, and a dummy head for the result with tail at it.
2. While both pointers are non-null: if p.val < q.val advance p; if p.val > q.val advance q.
3. Otherwise append a new node with p.val after tail, move tail, and advance both p and q.
4. Return dummy.next.

Why it works

When p.val < q.val, every remaining value of the second list is at least q.val, so p's value has no partner left and can be skipped; symmetrically for q. Equal values are matched one copy from each list, so a value is emitted exactly min(a, b) times, in sorted order.

Complexity

• Time — O(n + m)
• Space — O(k) for the k result nodes

Pitfalls

• Build new nodes; relinking the input nodes would change the original lists.
• Advance both pointers on a match, otherwise a single copy would be counted repeatedly.
• The result can be empty.

Reference solution

Python

from typing import Optional

def findIntersection(head1: Optional[ListNode], head2: Optional[ListNode]) -> Optional[ListNode]:
    dummy = ListNode(0)
    tail = dummy
    p, q = head1, head2
    while p and q:
        if p.val < q.val:
            p = p.next
        elif p.val > q.val:
            q = q.next
        else:
            tail.next = ListNode(p.val)
            tail = tail.next
            p, q = p.next, q.next
    return dummy.next

Java

public static ListNode findIntersection(ListNode head1, ListNode head2) {
    ListNode dummy = new ListNode(0), tail = dummy;
    ListNode p = head1, q = head2;
    while (p != null && q != null) {
        if (p.val < q.val) p = p.next;
        else if (p.val > q.val) q = q.next;
        else {
            tail.next = new ListNode(p.val);
            tail = tail.next;
            p = p.next;
            q = q.next;
        }
    }
    return dummy.next;
}

C++

ListNode* findIntersection(ListNode* head1, ListNode* head2) {
    ListNode dummy(0);
    ListNode* tail = &dummy;
    ListNode *p = head1, *q = head2;
    while (p && q) {
        if (p->val < q->val) p = p->next;
        else if (p->val > q->val) q = q->next;
        else {
            tail->next = new ListNode(p->val);
            tail = tail->next;
            p = p->next;
            q = q->next;
        }
    }
    return dummy.next;
}

JavaScript

var findIntersection = function(head1, head2) {
    var dummy = new ListNode(0), tail = dummy;
    var p = head1, q = head2;
    while (p !== null && q !== null) {
        if (p.val < q.val) p = p.next;
        else if (p.val > q.val) q = q.next;
        else {
            tail.next = new ListNode(p.val);
            tail = tail.next;
            p = p.next;
            q = q.next;
        }
    }
    return dummy.next;
};

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

More two pointers problems

• Nth Node From End of Linked List Easy
• Middle of the Linked List Easy
• Palindrome Linked List Easy
• Remove Duplicates from Sorted List Easy
• Merge Two Sorted Lists Easy
• Two Sum IV - Input is a BST Easy