面试题37 ：两个链表的第一个公共结点

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

可见，遇到类似链表这样的题目，应该思考结构，并且画出链表。

我们想到，如果从后往前比较，如果遇到了不同的节点，那么前一个相同的节点就是第一个公共节点。“后进先出”，想到用栈。于是用两个辅助站，如果链表的长度分别是m和n，那么空间复杂度和时间复杂度都是O(m+n)。

和最开始的蛮力法相比，时间效率得到了提高，相当于是用空间消耗换取了时间效率。

代码实现：

# -*- coding:utf-8 -*-
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def FindFirstCommonNode(self, pHead1, pHead2):
        length1 = self.GetLength(pHead1)
        length2 = self.GetLength(pHead2)
        gap = length1 - length2

        if gap > 0:
            pHead1_next = pHead1.next
            for i in range(1,gap):
                pHead1_next = pHead1_next.next
            pHead1 = pHead1_next
        if gap < 0:
            gap = gap * -1
            pHead2_next = pHead2.next
            for i in range(1, gap):
                pHead2_next = pHead2_next.next
            pHead2 = pHead2_next

        same_node = self.SameNode(pHead1,pHead2)
        return same_node


    #定义一个函数，输入两个相同长度链表的头结点，返回第一个公共节点
    #若没有公共节点呢？暂时定为返回None
    def SameNode(self,head1,head2):
        #长度为0
        if head1 == None or head2 == None:
            return None

        #长度为1
        if head1.val == head2.val:
            return head1

        #长度大于1
        head1_next = head1.next
        head2_next = head2.next
        same_node = None
        while head1_next != None and head2_next != None:
            if head1_next.val == head2_next.val:
                same_node = head1_next
                break
            else:
                head1_next = head1_next.next
                head2_next = head2_next.next
        return same_node

    #定义一个函数，获得链表的长度
    def GetLength(self,head):
        if head == None:
            return 0
        else:
            length = 1
            next_node = head.next
            while next_node != None:
                length += 1
                next_node = next_node.next
            return length

node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node4 = ListNode(4)
node5 = ListNode(5)
node6 = ListNode(6)
node7 = ListNode(7)

node1.next = node2
node2.next = node3
node3.next = node6
node6.next = node7
node4.next = node5
node5.next = node6

S = Solution()
print(S.FindFirstCommonNode(node1,node4))