Technical Interview Question:

You are given two linked lists, list1 and list2, each containing distinct integers in non-decreasing order. Write a function to find the intersection of the two linked lists and return a new linked list containing the intersection.

Function Signature:

class ListNode:
    def __init__(self, value=0, next=None):
        self.value = value
        self.next = next

def intersection(list1: ListNode, list2: ListNode) -> ListNode:
    pass

Example:

Input:

list1: 1 -> 2 -> 3 -> 4
list2: 2 -> 4 -> 6 -> 8

Output:

Intersection: 2 -> 4

Answer:

Here's a step-by-step explanation of the approach to solve this problem:

1. Initialize an empty result linked list to store the intersection.

2. Initialize two pointers ptr1 and ptr2 to head nodes of list1 and list2 respectively.

3. Traverse both linked lists by comparing the values at ptr1 and ptr2.

   • If ptr1.value == ptr2.value, add the value to the result linked list and move both pointers to the next nodes.
   • If ptr1.value > ptr2.value, move ptr2 to its next node.
   • If ptr1.value < ptr2.value, move ptr1 to its next node.

4. Repeat step 3 until either of the two pointers reaches the end of its respective list.

5. Return result linked list as the intersection of the two input linked lists.

Python Implementation:

def intersection(list1: ListNode, list2: ListNode) -> ListNode:
    result_head = ListNode()
    result_tail = result_head
    
    ptr1, ptr2 = list1, list2
    
    while ptr1 and ptr2:
        if ptr1.value == ptr2.value:
            result_tail.next = ListNode(ptr1.value)
            result_tail = result_tail.next
            ptr1 = ptr1.next
            ptr2 = ptr2.next
        elif ptr1.value < ptr2.value:
            ptr1 = ptr1.next
        else:
            ptr2 = ptr2.next

    return result_head.next

This implementation uses two pointers to traverse the input linked lists and build the resulting linked list containing the intersection of the input lists. It has a time complexity of O(m + n), where m and n are the lengths of list1 and list2 respectively.