面试真题

结论：求两单链表相交的起始节点，最优用双指针法，时间O(n)空间O(1)。核心要点：设链表A长度a+c，B长度b+c，c为公共尾部；指针pA从A头走，到尾后跳到B头；pB从B头走，到尾后跳到A头；因pA走a+c+b，pB走b+c+a，步数相等，必在第一个交点相遇（无交则同为空）。注意相交是比较节点引用而非值；不可直接比较值因可能有重复值。示例：A:1->2->3->4, B:5->3->4，交点为3。