1, Title Description

Enter two acyclic single linked lists and find their first common node( Note: because the incoming data is a linked list, the prompt of error test data is displayed in other ways to ensure that the incoming data is correct)

Example 1

Input: {1,2,3}, {4,5}, {6,7}

Return value: {6,7}

Note: the first parameter {1,2,3} represents the non-public part of the first linked list, the second parameter {4,5} represents the non-public part of the second linked list, and the last {6,7} represents the public part of the two linked lists... These three parameters will finally be assembled into two two acyclic single linked lists with public nodes in the background

Example 2

Input: {1}, {2,3}, {}

Return value: {}

Note: the two linked lists have no public nodes, return null, and print {}

2, Problem solving ideas

(I)

Two intersecting linked lists are Y-shaped. You can start from the tail of two linked lists at the same time. The last same node is the first same node of the linked list. It can be realized by stack. The temporal complexity is O(m+n), and the spatial complexity is O(m+n)

class Solution: def FindFirstCommonNode(self , pHead1 , pHead2 ): # write code here while not pHead1 : return pHead1 while not pHead1: return pHead2 if not pHead1 or not pHead2: return None stack1 = [] stack2 = [] while pHead1: stack1.append(pHead1) pHead1 = pHead1.next while pHead2: stack2.append(pHead2) pHead2 = pHead2.next first = None while stack1 and stack2: top1 = stack1.pop() top2 = stack2.pop() if top1 is top2: first = top1 else: break return first

(2) Double stack

Press the elements in the linked list into the two stacks in turn, and then throw one element from the two stacks at a time until the thrown nodes are the same. The returned elements are public

class Solution: def FindFirstCommonNode(self, pHead1, pHead2): # write code here lst1 = [] lst2 = [] result = [] if not pHead1 or not pHead2: return None p1 = pHead1 p2 = pHead2 while p1: lst1.append(p1) p1 = p1.next while p2: lst2.append(p2) p2 = p2.next while lst1 and lst2: node1 = lst1.pop() node2 = lst2.pop() if node1 == node2: result.append(node1) if result: node = result.pop() return node

(3) ifelse statement

No additional space is required to store the linked list. There is no need to know the length of the linked list in advance. Look at the following linked list example: 0-1-2-3-4-5-null a-b-4-5-null

The ifelse statement of the code, for a pointer p1, actually makes it run the linked list, and the length becomes the same.

If there is a common node, the part where the pointers go to the end together must overlap. Look at the path of the pointer below.

p1: 0-1-2-3-4-5-null (ifelse encountered at this time) - a-b-4-5-null

P2: a-b-4-5-null (ifelse encountered at this time) 0-1-2-3-4-5-null

Therefore, the length of the linked list to be traversed by the two pointers is the same!

class Solution: def FindFirstCommonNode(self, pHead1, pHead2): p1,p2=pHead1,pHead2 while p1!=p2: p1 = p1.next if p1 else pHead2 p2 = p2.next if p2 else pHead1 return p1

Traverse the two linked lists respectively, save the nodes into two arrays, and then pop the two arrays respectively. If the first pair of different nodes is found, the previous node can be returned directly.

class Solution: def FindFirstCommonNode(self, pHead1, pHead2): listA, listB = [], [] if not pHead2 and not pHead1: return None while pHead1: listA.append(pHead1) pHead1 = pHead1.next while pHead2: listB.append(pHead2) pHead2 = pHead2.next listA.reverse() listB.reverse() length = min(len(listB), len(listA)) temp=None for i in range(length): nodeA = listA.pop(0) nodeB = listB.pop(0) if nodeA == nodeB: temp = nodeA else: break return temp