Given the heads of two singly linked lists, return the node at which the two lists intersect. If the two linked lists do not intersect, return None. The lists must retain their original structure after the function returns. The intersection is defined by reference, not by value: if two nodes have the same value but are not the same node in memory, they do not count as intersecting. There are no cycles in either list.
Example 1
Input: # Example 1: Intersect at node with value 7 # List1: 2 -> 3 -> 7 -> 8 # List2: 5 -> 7 -> 8 # Intersection at node with value 7 # Setup: node8 = ListNode(8) node7 = ListNode(7, node8) head1 = ListNode(2, ListNode(3, node7)) head2 = ListNode(5, node7) get_intersection_node(head1, head2)
Output: node7
Explanation: Both lists intersect at node7 (value 7).
Example 2
Input: # Example 2: No intersection # List1: 10 -> 20 -> 30 # List2: 40 -> 50 head1 = ListNode(10, ListNode(20, ListNode(30))) head2 = ListNode(40, ListNode(50)) get_intersection_node(head1, head2)
Output: None
Explanation: Lists do not intersect.
Example 3
Input: # Example 3: Intersect at last node # List1: 1 -> 2 -> 3 # List2: 4 -> 3 node3 = ListNode(3) head1 = ListNode(1, ListNode(2, node3)) head2 = ListNode(4, node3) get_intersection_node(head1, head2)
Output: node3
Explanation: Both lists intersect at node3 (value 3).
Constraints
Case 1
Input: # Test 1: Intersect at node with value 100 node200 = ListNode(200) node100 = ListNode(100, node200) head1 = ListNode(1, ListNode(2, node100)) head2 = ListNode(50, node100) get_intersection_node(head1, head2)
Expected: node100
Case 2
Input: # Test 2: No intersection, single node lists head1 = ListNode(5) head2 = ListNode(6) get_intersection_node(head1, head2)
Expected: None
Case 3
Input: # Test 3: Intersect at first node node10 = ListNode(10) head1 = node10 head2 = node10 get_intersection_node(head1, head2)
Expected: node10