本题来自《剑指offer》 两个链表中的第一个公共节点
题目：
输入两个链表，找出它们的第一个公共结点。
思路：
交叉链表形式像Y形，这样两个分叉长短不一致，首先分别统计各自的长短，分叉为5和4那么，相差1个节点，让多的那个先走1个节点，之后同时遍历，当值相等即是公共节点。
Python Code：
# -*- coding:utf-8 -*- # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def FindFirstCommonNode(self, pHead1, pHead2): if not pHead1 or not pHead2: #empty node judgement return None m = 0 #the length of list phead1 M = pHead1 while M.next: #loop list phead1 m += 1 M = M.next #the next node of phead1 n = 0 #the lengteh of list phead2 N = pHead2 while N.next: #loop list phead2 n += 1 N = N.next #the next node of phead2 if m > n: #if list phead1 is longer than list phead2 for i in range(m - n): #traversing m-n node in advance pHead1 = pHead1.next #the next node of phead1 elif n > m: #same as above for i in range(n - m): pHead2 = pHead2.next else : pass while pHead1 and pHead2: #traverse at the same time if pHead1.val == pHead2.val: #during this process,only when the two value is equal return pHead1 #return one of them elif not pHead1.next or not pHead2.next: #when there is no equal value when travesing to the end return None #there are no public node else: pHead1 = pHead1.next #the next node of the list phead1 pHead2 = pHead2.next #same as above