Shulou(Shulou.com)06/01 Report--

This article mainly introduces how to find the first common node of the two linked lists by LeetCode. It is very detailed and has a certain reference value. Friends who are interested must read it!

Topic description

Enter two linked lists to find their first common node.

If the two linked lists do not intersect, return null. After the results are returned, the two linked lists must remain in their original structure. It can be assumed that there are no loops in the entire linked list structure. The program satisfies O (n) time complexity as far as possible, and only O (1) memory is used. Sample topic example

Input: intersectVal = 8, listA = [4 intersectVal = 8, listA = 4], listB =], skipA = 2, skipB = 3 output: Reference of the node with value = 8 input explanation: the value of the intersecting node is 8 (note that it cannot be 0 if the two lists intersect). Starting from their respective headers, the linked list An is [4 magi 1, 8, 4, 5], and the linked list B is [5, 0, 1, 1, 8, 4, and 5]. In A, there are 2 nodes in front of intersecting nodes; in B, there are 3 nodes in front of intersecting nodes. Think about how to get the results with only O (1) memory. An easy way to think of the solution is to first traverse one of the linked lists, store the nodes in the collection, and then traverse the other linked list to see if the nodes exist in the collection. In this way, although the time complexity is O (N), the space complexity is also O (N), which does not meet the requirements of the topic to re-observe the example of the topic. Assuming that the length of the shared part of the linked list An and B is shared, and the length of the exclusive part in front of each is an and b, then the total length of An is a+shared, and the total length of B is b+shared. According to the exchange law, the length of An is equal to the length of b+shared+a+shared, that is, a+shared+b+shared = b+shared+a+shared according to the above formula. We can define two pointers, starting from the beginning of An and B, and then changing to the starting point of another linked list: if An and B have an intersection, it is obvious that the two pointers will meet at the intersection and go through the rest of the shared together. If there is no intersection, the two pointers can only go to the last empty node together, so return null at this time. Pay special attention to this point. When we traverse to the last node, we can't jump directly to the beginning. Instead, we should first go to the empty node after the end, and then jump to the beginning of another linked list. Because if you do not enter the empty node, you will never be able to jump out of the loop if there is no intersection (the empty node after the end will never be equal, and the corresponding nodes of the two pointers will never be equal) complexity time complexity O (N): only need to traverse the space complexity O (1): only a few variable codes are defined: class Solution:

Def getIntersectionNode (self, headA: ListNode

HeadB: ListNode)-> ListNode:

A, b = headA, headB

While a! = b:

# an if you reach the empty node after the end of A, set it to the starting point of B and re-traverse

A = headB if not an else a.next

# b if you reach the empty node after the end of B, set it to the starting point of An and re-traverse

B = headA if not b else b.next

Return a

These are all the contents of the article "how to find the first common node of two linked lists by LeetCode". Thank you for reading! Hope to share the content to help you, more related knowledge, welcome to follow the industry information channel!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.