leetCode The first 160 topic Intersecting list
link ：https://leetcode-cn.com/problems/intersection-of-two-linked-lists
Here are two head nodes of the single linked list headA and headB , Please find out and return the starting node where two single linked lists intersect . If two linked lists do not have intersecting nodes , return null .
Figure two linked lists at the node c1 Start meeting ：
Subject data Guarantee There is no ring in the whole chain structure .
Be careful , Function returns the result , Linked list must Keep its original structure .
Custom profiling ：
Evaluation system The input is as follows （ The program you designed Do not apply This input ）：
intersectVal - The value of the starting node of the intersection . If there are no intersecting nodes , This value is 0
listA - The first list
listB - The second list
skipA - stay listA in （ Start from the beginning ） Number of nodes jumping to cross nodes
skipB - stay listB in （ Start from the beginning ） Number of nodes jumping to cross nodes
The evaluation system will create a linked data structure based on these inputs , And the two header nodes headA and headB The program passed to you . If the program returns the intersection node correctly , Then your solution will be Take it as the right answer .
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’
explain ： The value of the intersection node is 8 （ Be careful , If two linked lists intersect, they cannot be 0）.
Starting from the respective heads , Linked list A by [4,1,8,4,5], Linked list B by [5,6,1,8,4,5].
stay A in , There is... Before the intersection node 2 Nodes ; stay B in , There is... Before the intersection node 3 Nodes .
Example 2:
Input ：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output ：Intersected at ‘2’
explain ： The value of the intersection node is 2 （ Be careful , If two linked lists intersect, they cannot be 0）.
Starting from the respective heads , Linked list A by [1,9,1,2,4], Linked list B by [3,2,4].
stay A in , There is... Before the intersection node 3 Nodes ; stay B in , There is... Before the intersection node 1 Nodes .
Example 3：
Input ：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output ：null
explain ： Starting from the respective heads , Linked list A by [2,6,4], Linked list B by [1,5].
Because these two linked lists don't intersect , therefore intersectVal It has to be for 0, and skipA and skipB It could be any value .
The two lists don't intersect , Therefore return null .
Tips ：
listA The number of nodes in is m
listB The number of nodes in is n
1 <= m, n <= 3 * 104
1 <= Node.val <= 105
0 <= skipA <= m
0 <= skipB <= n
If listA and listB There is no point of intersection ,intersectVal by 0
If listA and listB There are intersections ,intersectVal == listA[skipA] == listB[skipB]
Advanced ： Can you design a time complexity O(m + n) 、 Just use O(1) Memory solutions ？
Analyze the problem , If you have no thoughts , Think of the law of violence , Direct will A All nodes of are brought in one by one B, If you find the same , Then prove that the two intersect
class Solution: def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode: if headA == None or headB == None: return None while headA != None: tempB = headB while tempB != None: if headA != tempB: tempB = tempB.next else: return tempB headA = headA.next return NoneIn this way, the time complexity reaches O(n*m), It will inevitably lead to timeout
Might as well introduce hash map , Not in this place python Dictionary to achieve hash map, It should be implemented in collections
First the A All nodes of are stored in hash map
Traverse B Every node of , If in hash map There is , Then prove that this is the intersection
## python3
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
hash_map = set()
if headA == None or headB == None:
return None
while headA != None:
hash_map.add(headA)
headA = headA.next
while headB != None:
if headB in hash_map:
return headB
else:
headB = headB.next
return None
Advanced requires us to design a time complexity O(m + n) 、 Just use O(1) Memory solutions . that hash map The space complexity is not satisfied by the introduction of .
At this time, you might as well use double finger needling , stay A and B Set a pointer at the beginning of the .
Then move the pointer at the same time , Then one end will traverse first
take A The pointer of moves to B The beginning of , Continue traversing , after B Will also be traversed
take B Move to A The beginning of
At this point, the two pointers will be in the same position , Keep moving the pointer , Find the node of the confluence .
This is actually a very simple mathematical reasoning , Because if there is a difference in length , Then the difference in the length of the linked list is just as good as the multiple steps of a node .
# python3
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
if headA == None or headB == None:
return None
tempA = headA
tempB = headB
while tempA != tempB:
tempA = headB if tempA == None else tempA.next
tempB = headA if tempB == None else tempB.next
return tempA
Of course, we can also directly calculate the length of the two linked lists , Calculate the difference in length , Let the long linked list go through those extra nodes first , Then find the converging node
## python3
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
if headA == None or headB == None:
return None
len1 = 0
len2 = 0
diff = 0
tempA = headA
tempB = headB
while headA != None:
len1 += 1
tempA = tempA.next
while headB != None:
len2 += 1
tempB = tempB.next
if len1 < len2: ## send tempA Point to a longer linked list , Convenient for subsequent movement
tempA = headB
tempB = headA
diff = len2 - len1
else:
tempA = headA
tempB = headB
diff = len1 - len2
for i in range(diff):
tempA = tempA.next
while tempA != None and tempB != None:
if tempA == tempB:
return tempA
else:
headA = headA.next
headB = headB.next
return None
