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