核心知识点：双指针法与链表对齐技巧

在解决链表问题时，双指针法是常用且高效的策略。本题的关键在于如何处理两个长度不同的链表，使其在第二次遍历时能够同时到达交点。

双指针法原理

双指针法通过维护两个指针，使其在特定条件下移动，从而简化问题。在本题中，我们需要让两个指针在第二次遍历时对齐。

链表对齐技巧

由于两个链表长度不同，直接遍历无法同时到达交点。通过让指针在遍历完一个链表后切换到另一个链表的头部，可以实现长度对齐。具体来说：

• 指针 pA 遍历完链表 A 后，切换到链表 B 的头部。
• 指针 pB 遍历完链表 B 后，切换到链表 A 的头部。
  这样，两个指针在第二次遍历时，走过的总路程相同，从而能够同时到达交点。

题目解析：LeetCode 160. 相交链表

题目描述

给你两个单链表的头节点 headA 和 headB，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null。

示例

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：链表 A 和链表 B 在节点 8 处相交。

代码实现

# Definition for singly-linked list.  
# class ListNode:  
#     def __init__(self, x):  
#         self.val = x  
#         self.next = None  

class Solution:  
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:  
        pA, pB = headA, headB  
        while pA != pB:  
            pA = pA.next if pA else headB  
            pB = pB.next if pB else headA  
        return pA  

复杂度分析

• 时间复杂度：O(m+n)，其中 m 和 n 分别是两个链表的长度。每个指针最多遍历两个链表各一次。
• 空间复杂度：O(1)，只使用了常数级别的额外空间。

总结

通过双指针法和链表对齐技巧，我们可以在不改变链表结构的前提下，高效地找到两个链表的相交节点。这种方法不仅时间复杂度低，而且空间复杂度也为常数级别，是解决此类问题的理想选择。