输入两个链表， 找出它们的第一个公共节点。
公共结点的意思是相同的点，不仅值相同，next也相同，包括公共结点后面的节点也是完全相同，所以可以把两条链表看成Y字型了，某一个结点后面的点全部一样。例如3->2->1和4->2->1，2就是他们的第一个公共结点。
我们先把全部结点分别压入两个栈，利用栈的特性后进先出特性，同时pop出栈，一开始两边的元素肯定是相同的，当遇到不同的元素时，肯定已经遇到了最后一个节点，那就结束找到commonNode
class LinkNode(): def __init__(self): self.value = None self.next = None class Solution(): def creatLinkA(self) -> LinkNode: node1 = LinkNode() node1.value = 3 node1.next = None node2 = LinkNode() node2.value = 2 node2.next = node1 node3 = LinkNode() node3.value = 1 node3.next = node2 return node3 def creatLinkB(self) -> LinkNode: node1 = LinkNode() node1.value = 3 node1.next = None node2 = LinkNode() node2.value = 2 node2.next = node1 node3 = LinkNode() node3.value = 5 node3.next = node2 return node3 def searchFirstLinkNode(self, headA:LinkNode, headB:LinkNode) ->LinkNode: if headA is None: return None if headB is None: return None listA = [] listB = [] while headA is not None: listA.append(headA) headA = headA.next while headB is not None: listB.append(headB) headB = headB.next commonNode = None while listB and listA: nodeB = listB.pop() nodeA = listA.pop() if nodeA.value != nodeB.value: return commonNode else: commonNode = nodeA return None solu = Solution() headA = solu.creatLinkA() headB = solu.creatLinkB() endNode = solu.searchFirstLinkNode(headA,headB) print(endNode.value)
