leetcode链表之如何查找两个链表的第一个公共节点

问题描述:
给定两个单链表，链表可能存在公共节点，即两个链表在某个节点处开始相交。实现一个函数，找到两个链表的第一个公共节点。若链表无公共节点，返回null。

方法一：暴力法
1. 遍历链表A的每一个节点a1、a2、a3...an，对于每个节点，遍历链表B的每一个节点b1、b2、b3...bn，去寻找是否有相同的节点。
2. 若找到相同的节点，则该节点即为第一个公共节点。

<pre class="line-numbers language-python">
def getIntersectionNode(headA, headB):
    if headA is None or headB is None:
        return None
    nodeA = headA
    while nodeA:
        nodeB = headB
        while nodeB:
            if nodeA == nodeB:
                return nodeA
            nodeB = nodeB.next
        nodeA = nodeA.next
    return None
</code>

复杂度分析:
- 时间复杂度：O(m*n)，其中m和n分别是链表A和链表B的长度。
- 空间复杂度：O(1)。

方法二：双指针法
1. 创建两个指针pA和pB，初始时分别指向链表A和链表B的头节点。
2. 同时遍历两个链表，若遍历到链表末尾，则将指针重新指向另一个链表的头节点。当两个指针相等时，即找到第一个公共节点或者两个链表都为null。

<pre class="line-numbers language-python">
def getIntersectionNode(headA, headB):
    if headA is None or headB is None:
        return None
    pA = headA
    pB = headB
    while pA != pB:
        pA = pA.next if pA else headB
        pB = pB.next if pB else headA
    return pA
</code>

复杂度分析:
- 时间复杂度：O(m+n)，其中m和n分别是链表A和链表B的长度。
- 空间复杂度：O(1)。

方法三：计算链表长度
1. 遍历链表A和链表B，分别计算出它们的长度，设为m和n。
2. 长链表先走|m-n|步，然后两个链表同时遍历，直到找到第一个公共节点。

<pre class="line-numbers language-python">
def getIntersectionNode(headA, headB):
    if headA is None or headB is None:
        return None
    lenA = getLength(headA)
    lenB = getLength(headB)
    pA = headA
    pB = headB
    if lenA > lenB:
        for i in range(lenA - lenB):
            pA = pA.next
    else:
        for i in range(lenB - lenA):
            pB = pB.next
    while pA and pB:
        if pA == pB:
            return pA
        pA = pA.next
        pB = pB.next
    return None

def getLength(node):
    length = 0
    while node:
        node = node.next
        length += 1
    return length
</code>

复杂度分析:
- 时间复杂度：O(m+n)，其中m和n分别是链表A和链表B的长度。
- 空间复杂度：O(1)。