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

题目描述

输入两个链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）

解题思路

方法一：双指针

核心思想：两个指针分别遍历两个链表，当一个指针走到末尾时，切换到另一个链表。如果有公共节点，两个指针会在公共节点相遇。

方法二：长度差法

核心思想：先求两个链表的长度差，让长链表先走差值步，然后两个指针同时走。

时间复杂度：O(m + n) 空间复杂度：O(1)

Python 实现

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


# 方法一：双指针
def find_first_common_node(head1, head2):
    """
    双指针法找第一个公共节点
    """
    if not head1 or not head2:
        return None

    p1, p2 = head1, head2

    while p1 != p2:
        p1 = p1.next if p1 else head2
        p2 = p2.next if p2 else head1

    return p1


# 方法二：长度差法
def find_first_common_node_by_length(head1, head2):
    """
    长度差法找第一个公共节点
    """
    def get_length(head):
        length = 0
        while head:
            length += 1
            head = head.next
        return length

    len1 = get_length(head1)
    len2 = get_length(head2)

    # 长链表先走差值步
    long_head, short_head = (head1, head2) if len1 > len2 else (head2, head1)
    for _ in range(abs(len1 - len2)):
        long_head = long_head.next

    # 同时走，寻找公共节点
    while long_head and short_head:
        if long_head == short_head:
            return long_head
        long_head = long_head.next
        short_head = short_head.next

    return None


# 辅助函数：创建链表
def create_linked_list(arr):
    if not arr:
        return None
    head = ListNode(arr[0])
    p = head
    for val in arr[1:]:
        p.next = ListNode(val)
        p = p.next
    return head


# 测试代码
if __name__ == "__main__":
    # 创建两个有公共节点的链表
    # 链表1: 1->2->3->6->7
    # 链表2: 4->5->6->7
    # 公共节点: 6->7
    node6 = ListNode(6)
    node7 = ListNode(7)
    node6.next = node7

    head1 = ListNode(1)
    head1.next = ListNode(2)
    head1.next.next = ListNode(3)
    head1.next.next.next = node6

    head2 = ListNode(4)
    head2.next = ListNode(5)
    head2.next.next = node6

    common = find_first_common_node(head1, head2)
    if common:
        print(f"第一个公共节点的值: {common.val}")
    else:
        print("没有公共节点")

# 输出:
# 第一个公共节点的值: 6

图解

双指针法示例:
链表1: 1 -> 2 -> 3 -> 6 -> 7 -> None
链表2: 4 -> 5 -> 6 -> 7 -> None

p1遍历链表1: 1,2,3,6,7,None
p2遍历链表2: 4,5,6,7,None

p1到达None后，切换到链表2
p2到达None后，切换到链表1

继续:
p1: 4,5,6
p2: 1,2,3,6

在节点6处相遇！

原理:
设链表1长度为l1，链表2长度为l2，公共部分长度为l
p1走l1+l2步，p2走l2+l1步
两个指针走过的总距离相同，必然在公共节点相遇