Difficulty: Easy | Acceptance: 63.70% | Paid: No Topics: Hash Table, Linked List, Two Pointers
Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.
The test cases are generated such that there are no cycles anywhere in the entire linked structure.
Note that the linked lists must retain their original structure after the function returns.
Custom Judge:
The inputs to the judge are given as follows (your program is not given these inputs):
intersectVal - The value of the node where the intersection occurs. This is 0 if there is no intersected node. listA - The first linked list. listB - The second linked list. skipA - The number of nodes to skip ahead in listA (starting from the head) to get to the intersected node. skipB - The number of nodes to skip ahead in listB (starting from the head) to get to the intersected node. The judge will then create the linked structure based on these inputs and pass the two heads, headA and headB to your program. If you correctly return the intersected node, then your solution will be accepted.
- Examples
- Constraints
- Brute Force with Hash Set
- Length Difference Method
- Two Pointers Technique
Examples
Example 1
Input:
intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
Output:
Intersected at '8'
Explanation: The intersected node’s value is 8 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,6,1,8,4,5]. There are 2 nodes before the intersection node in A; There are 3 nodes before the intersection node in B.
- Note that your solution must return the node, not the value.
Example 2
Input:
intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output:
Intersected at '2'
Explanation: The intersected node’s value is 2 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [1,9,1,2,4]. From the head of B, it reads as [3,2,4]. There are 3 nodes before the intersection node in A; There are 1 node before the intersection node in B.
Example 3
Input:
intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output:
null
Explanation: The two lists do not intersect, so return null.
Constraints
- The number of nodes of listA is in the m.
- The number of nodes of listB is in the n.
- 1 <= m, n <= 3 * 10^4
- 1 <= Node.val <= 10^5
- 0 <= skipA <= m
- 0 <= skipB <= n
- intersectVal is 0 if listA and listB do not intersect.
- intersectVal == listA[skipA] == listB[skipB] if listA and listB intersect.
Brute Force with Hash Set
Intuition Store all nodes from the first list in a hash set, then traverse the second list and check if any node exists in the set.
Steps
- Traverse listA and store all node references in a hash set.
- Traverse listB and for each node, check if it exists in the hash set.
- Return the first node from listB that is found in the set, or null if no intersection exists.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
seen = set()
curr = headA
while curr:
seen.add(curr)
curr = curr.next
curr = headB
while curr:
if curr in seen:
return curr
curr = curr.next
return NoneComplexity
- Time: O(m + n) where m and n are the lengths of the two lists
- Space: O(m) or O(n) for storing nodes in the hash set
- Notes: Simple to implement but uses extra space proportional to the size of one list.
Length Difference Method
Intuition Calculate the lengths of both lists, move the pointer of the longer list ahead by the difference, then traverse both lists simultaneously until they meet.
Steps
- Calculate the length of both lists.
- Find the absolute difference between the lengths.
- Move the pointer of the longer list ahead by the difference.
- Move both pointers together until they either meet (intersection) or reach null (no intersection).
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
def get_length(head):
length = 0
while head:
length += 1
head = head.next
return length
lenA = get_length(headA)
lenB = get_length(headB)
currA, currB = headA, headB
if lenA > lenB:
for _ in range(lenA - lenB):
currA = currA.next
else:
for _ in range(lenB - lenA):
currB = currB.next
while currA and currB:
if currA == currB:
return currA
currA = currA.next
currB = currB.next
return NoneComplexity
- Time: O(m + n) where m and n are the lengths of the two lists
- Space: O(1) constant extra space
- Notes: Optimal space complexity but requires two passes to calculate lengths.
Two Pointers Technique
Intuition Use two pointers that traverse both lists. When one pointer reaches the end, it switches to the head of the other list. They will meet at the intersection node if it exists, or both reach null simultaneously if no intersection.
Steps
- Initialize two pointers, one for each list.
- Move both pointers forward one step at a time.
- When a pointer reaches the end of its list, redirect it to the head of the other list.
- The pointers will meet at the intersection node, or both become null if no intersection exists.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
if not headA or not headB:
return None
pA, pB = headA, headB
while pA != pB:
pA = pA.next if pA else headB
pB = pB.next if pB else headA
return pAComplexity
- Time: O(m + n) where m and n are the lengths of the two lists
- Space: O(1) constant extra space
- Notes: Most elegant solution with optimal time and space complexity. Each pointer traverses at most m + n nodes.