相交链表（LeetCode）

题目

解题

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


def getIntersectionNode(headA, headB):
    """
    找到两个单链表相交的起始节点。

    参数:
    headA (ListNode): 第一个链表的头节点。
    headB (ListNode): 第二个链表的头节点。

    返回值:
    ListNode: 相交的起始节点，如果不相交则返回 None。
    """
    if not headA or not headB:
        return None

    # 初始化两个指针
    pA, pB = headA, headB

    # 当两个指针相等时，表示找到了相交点
    while pA != pB:
        # 如果 pA 走到尽头，则开始遍历 headB
        pA = pA.next if pA else headB
        # 如果 pB 走到尽头，则开始遍历 headA
        pB = pB.next if pB else headA

    return pA


# 测试函数
def test_getIntersectionNode():
    # 创建链表
    # A链表: 4 -> 1
    #               \
    #                8 -> 4 -> 5
    #               /
    # B链表:    5 -> 0 -> 1
    # 相交节点为 8

    # 创建交点和后续部分
    intersection = ListNode(8)
    intersection.next = ListNode(4)
    intersection.next.next = ListNode(5)

    # 创建链表A
    headA = ListNode(4)
    headA.next = ListNode(1)
    headA.next.next = intersection

    # 创建链表B
    headB = ListNode(5)
    headB.next = ListNode(0)
    headB.next.next = ListNode(1)
    headB.next.next.next = intersection

    # 找到相交节点
    result = getIntersectionNode(headA, headB)
    if result:
        print(f"相交的起始节点值: {result.val}")
    else:
        print("没有相交节点")


# 运行测试函数
test_getIntersectionNode()