36. 两个链表的第一个公共结点

36. 两个链表的第一个公共结点

题目描述
输入两个链表，找出它们的第一个公共结点。

思路
两个链表有交叉的部分，则交叉部分为公共节点，由于链表的每个节点只有唯一的一个next，所以，链表交叉后，之后的节点全部是公共节点，不会再有分叉了。
思路一：
将两个链表合并，形成pHead1+pHead2和pHead2+pHead1两个链表，这两个链表长度相等，后面的几个节点必定是相同的公共节点，分别对两个链表进行遍历，并比较当前节点，如果相等则说明这个是公共节点，返回即可得第一个公共节点。
思路二：
还有一种思路是获取链表的长度，将长的链表长出来的部分删(遍历)掉，然后再跟短链表一起遍历。由于没有给定求链表长度的函数，所以要自定义一个。

代码实现
思路一：

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def FindFirstCommonNode(self, pHead1, pHead2):
        # write code here
        if pHead1 == None or pHead2 == None:
            return None
        else:
            node1, node2 = pHead1, pHead2
            while(node1 != node2):
                # 相当于遍历pHead1+pHead2
                if(node1 != None):
                    node1 = node1.next
                else:
                    node1 = pHead2
                # 相当于遍历pHead2+pHead1
                if(node2 != None):
                    node2 = node2.next
                else:
                    node2 = pHead1
            return node1 # 返回node2也可以

思路二：

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def FindFirstCommonNode(self, pHead1, pHead2):
        # write code here
        # 获取链表长度
        def getLenth(pHead):
            if pHead == None:
                return 0
            lenth = 0
            while(pHead.next != None):
                pHead = pHead.next
                lenth += 1
            return lenth

        if pHead1 == None or pHead2 == None:
            return None
        else:
            node1, node2 = pHead1, pHead2
            len1 = getLenth(node1)
            len2 = getLenth(node2)
            longer,shoter,lenDif = None,None,0
            if len1>len2:
                longer,shoter,lenDif = node1,node2,len1-len2
            else:
                longer,shoter,lenDif = node2,node1,len2-len1
            # 长的链表长出来的部分删(遍历)掉
            for i in range(lenDif):
                longer = longer.next
            # 两个等长的链表一起遍历
            while(longer != shoter):
                longer = longer.next
                shoter = shoter.next
            return longer # 返回shoter也可以