algoadvance

The problem is to find the intersection node of two singly linked lists. The intersection node is defined as the node that both linked lists share. If there is no intersection, return None.

Clarifying Questions

1. What should be the output if both linked lists do not intersect?
   • The output should be None.
2. Can the linked lists be empty?
   • Yes, either or both linked lists can be empty, and in that case, the output should be None.
3. Is it guaranteed that the lists will only intersect at a single node (or not at all)?
   • Yes, if they intersect, they will do so at a single node, and all nodes following that will be common to both lists.
4. What should be returned, the intersection node itself or its value?
   • Return the intersection node itself.

Strategy

1. Approach Explanation:
   • Initial Idea: We will first determine the lengths of both linked lists. We will then adjust the starting point of the longer list to match the length of the shorter list.
   • Traversal and Comparison: We simultaneously traverse both lists from their respective starting points. The first node at which the two lists intersect is the required node.
2. Steps:
   1. Calculate the lengths of both linked lists.
   2. Adjust the head pointer of the longer linked list to make their lengths equal.
   3. Traverse both lists together until a common node is found or until reaching the end of the lists (indicating no intersection).

Code

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def getIntersectionNode(headA: ListNode, headB: ListNode) -> ListNode:
    if not headA or not headB:
        return None

    def get_length(head):
        length = 0
        while head:
            length += 1
            head = head.next
        return length

    lenA = get_length(headA)
    lenB = get_length(headB)

    # Adjust head pointers to the same starting point
    while lenA > lenB:
        headA = headA.next
        lenA -= 1
    while lenB > lenA:
        headB = headB.next
        lenB -= 1

    # Traverse both lists concurrently
    while headA and headB:
        if headA == headB:
            return headA
        headA = headA.next
        headB = headB.next

    return None

Time Complexity

• Time Complexity: O(N + M), where N is the length of the first linked list and M is the length of the second linked list.
  • Calculating the lengths requires O(N + M).
  • Aligning the lists by advancing the pointer of the longer list is O(N) or O(M).
  • The final traversal also requires O(min(N, M)) time.
• Space Complexity: O(1), since we only use a constant amount of extra space.

This approach ensures that no extra space is used, and it traverses each list only a limited number of times, providing an efficient solution.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?