How to Answer: Where do the two linked lists intersect?
Advice and answer examples written specifically for a Python Intermediate Level Linked Lists job interview.
3. Where do the two linked lists intersect?
This question focuses on working with Python lists.
You are given heads of two singly linked lists: headA and headB. Your task is to return the node at which they intersect each other. If they don’t intersect, return null.
It is guaranteed that there is no cycle in any of the lists. Please note the linked lists MUST retain their original structure after the function returns.
/*Example*/
Given lists:
headA: 4 -> 1
\
8 -> 7 -> 9
/
headB: 5 -> 2 -> 3 -> 10
Expected output: 8
Explanation: Since both of the lists intersect at node 8, we return 8
Given lists:
headA: 4 -> 1 -> 8 -> 4 -> 5
headB: 5 -> 2 -> 3 -> 8 -> 4 -> 5
Expected output: null
Explanation: The lists do not intersect.Solution:
Approach I (finding length):
First, we will find the lengths of the two lists using the function listLength. Then we will align headA and headB such that the length of the list after points headA and headB are the same. For the first example:
lenA = 5
lenB = 7
We move headB two steps ahead to point to the node with value 3 such that lengths after headA and headB are the same, that is 5.
After aligning the nodes, we iterate over both lists simultaneously and will find the same node. At each iteration, we advance both headA and headB if previous values were not equal. We break the loop as soon as the values of headA and headB are the same which means it is the intersection node.
If the lists do not intersect, the values of headA and headB will be null at last, which will break the loop and will return null.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def listLength(head: ListNode) -> int:
count = 0
while head:
head = head.next
count += 1
return count
def getIntersectionNode(headA: ListNode, headB: ListNode) -> ListNode:
lenA = listLength(headA)
lenB = listLength(headB)
while lenA > lenB:
lenA -= 1
headA = headA.next
while lenB > lenA:
lenB -= 1
headB = headB.next
while headA is not headB:
headA = headA.next
headB = headB.next
return headAn = length the linked list
Time complexity- O(n)
Space complexity- O(1)
Written by S. Kumar on May 22nd, 2021