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

Question

如果链表存在公共结点，则必然会出现从公共结点以后全部相同的情况，这样就先把两者的差值运行了即可。

要找出两个链表的第一个公共节点，可以使用双指针的方法。

• 首先，分别遍历两个链表，得到它们的长度。
• 然后，让长链表的指针先移动两个链表的长度差个节点。
• 最后，同时遍历两个链表，如果找到了相同的节点，就是第一个公共节点；如果遍历结束也没有找到相同的节点，说明两个链表没有公共节点。

以下是具体的实现代码：

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

def getIntersectionNode(headA: ListNode, headB: ListNode) -> ListNode:
    # 遍历链表得到长度
    def getLength(head: ListNode):
        length = 0
        while head:
            length += 1
            head = head.next
        return length

    # 指针移动
    def movePtr(head: ListNode, step: int):
        while step > 0:
            head = head.next
            step -= 1
        return head

    lenA = getLength(headA)
    lenB = getLength(headB)

    if lenA > lenB:
        headA = movePtr(headA, lenA - lenB)
    else:
        headB = movePtr(headB, lenB - lenA)

    while headA and headB:
        if headA == headB:
            return headA
        headA = headA.next
        headB = headB.next

    return None

在上述代码中，函数 getIntersectionNode 接受两个链表的头节点 headA 和 headB 作为输入，并返回第一个公共节点。函数中使用了两个辅助函数 getLength 用于计算链表的长度， movePtr 用于移动指针。

时间复杂度为 O(m+n)，其中 m 和 n 分别是两个链表的长度。