Intersection Of Two Linked Lists - Leetcode Solution

Problem Statement:

Write a program to find the node at which the intersection of two singly linked lists begins.

Example:

Input:

LinkedList1: 4 -> 1 -> 8 -> 4 -> 5 LinkedList2: 5 -> 0 -> 1 -> 8 -> 4 -> 5

Output:

Node at which intersection of two linked lists begins: 8

Explanation:

In the input, the linked lists intersect at node 8.

Solution:

Approach:

The problem can be solved using a 2-pointer approach. We can iterate over both the linked lists at the same time using two pointers. When one of the pointers reach the end of the linked list, we set that pointer to the head of the other linked list. So, the two pointers will always be the same length away from the intersection point of the linked lists. When the two pointers meet at the intersection node, we return that node.

Algorithm:

1. Traverse through the first linked list and compute the length of the list, store it in a variable called len1.

2. Traverse through the second linked list and compute the length of the list, store it in a variable called len2.

3. Compute the difference in lengths of the two linked lists. If len1 is greater than len2, set p1 to point to the head of the first linked list and move it forward by (len1 - len2) nodes. If len2 is greater than len1, set p2 to point to the head of the second linked list and move it forward by (len2 - len1) nodes.

4. Traverse through both linked lists at the same time using two pointers, p1 and p2. Stop when p1 and p2 point to the same node. Return the node.

Pseudo Code:

• Compute the length of the first linked list.
• Compute the length of the second linked list.
• Compute the difference in lengths of the two linked lists.
• Set p1 to the head of the first linked list and move it forward by (len1 - len2) nodes; set p2 to the head of the second linked list and move it forward by (len2 - len1) nodes.
• Traverse through both linked lists at the same time using the two pointers p1 and p2.
• Stop when p1 and p2 point to the same node.
• Return the node.

Implementation:

def getIntersectionNode(headA: ListNode, headB: ListNode) -> ListNode: lenA, lenB = 0, 0 p1, p2 = headA, headB

# Traverse through the first linked list and compute the length of the list
while p1:
    lenA += 1
    p1 = p1.next

# Traverse through the second linked list and compute the length of the list
while p2:
    lenB += 1
    p2 = p2.next

# Compute the difference in lengths of the two linked lists
diff = abs(lenA - lenB)

# Set p1 to the head of the first linked list
p1 = headA
# Move p1 forward by (lenA - lenB) nodes
if lenA > lenB:
    for i in range(diff):
        p1 = p1.next
else:
    p2 = headB
    for i in range(diff):
        p2 = p2.next

# Traverse through both linked lists at the same time using the two pointers p1 and p2
while p1 and p2:
    # Stop when p1 and p2 point to the same node
    if p1 == p2:
        return p1
    p1 = p1.next
    p2 = p2.next

return None

Time complexity: O(m + n) where m and n are the lengths of the two linked lists. Space complexity: O(1).

1