题解 | #两个链表的第一个公共结点#

NC66 两个链表的第一个公共结点

描述 输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）

数据范围： 0n≤1000 要求：空间复杂度 O(1)，时间复杂度 O(n)

思路：一、如果有公共节点，那么两链表的后面部分完全相同，所以可以从后往前遍历，直到两个不同。因为链表没法从后往前遍历，所以需要反转两个链表，之后两个反转链表从后往前遍历，用result记录当前节点，如果相等，将当前节点赋给result，如果不相等的，则result.next = None，然后再将这个公共链表反转。

二、如果有公共节点，那么两链表的后面部分完全相同，所以后面部门链表的长度是一样的，所以可以先遍历两个链表（也可以直接为了省时间用快指针遍历），分别记录两个链表的长度为l1、l2，然后计算长度差，如果l1更长，那么链表1先走l1-l2步，反之，l2先走l2-l1步，之后两个链表一起走，当两个链表值相同时返回当前节点。

方法二可能更简单，但是如果给的链表如果一个是{1，2，3，5，6，7}，另一个为{2，4，5，6，7}，这时候方法二返回2，方法一返回5，不知道2算不算公共节点，如果算，则方法二对，方法一错。如果不算，则方法二错，方法一对。

用的方法二测试通过了，但是看返回结果应该是方法一才是对的，所以说明不会给出我提到的测试样例

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

#
# 
# @param pHead1 ListNode类 
# @param pHead2 ListNode类 
# @return ListNode类
#
class Solution:
    def FindFirstCommonNode(self , pHead1 , pHead2 ):
        # write code here
        l1 = 0
        l2 = 0
        if (pHead1 == None) | (pHead2 == None):
            return None
        p1 = pHead1
        p2 = pHead2
        while (p1 != None) | (p2 != None):
            if p1 == p2:
                return p1
            if p1 != None:
                l1 += 1
                p1 = p1.next
            if p2 != None:
                l2 += 1
                p2 = p2.next
        p1 = pHead1
        p2 = pHead2
        n = l1
        if l1 > l2:
            for i in range(l1-l2):
                p1 = p1.next
            n = l2
        elif l2 > l1:
            for j in range(l2-l1):
                p2 = p2.next
        for k in range(n):
            if p1.val == p2.val:
                return p1
            p1 = p1.next
            p2 = p2.next
        return None