剑指Offer题解 - Day26

「剑指 Offer 52. 两个链表的第一个公共节点」

力扣题目链接[1]

输入两个链表，找出它们的第一个公共节点。

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

注意：

• 如果两个链表没有交点，返回 null。
• 在返回结果后，两个链表仍须保持原有的结构。
• 可假定整个链表结构中没有循环。
• 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

思路：

此题求两个链表的第一个公共节点。题目要求时间复杂度是O(n)，空间复杂度是O(1) ，这里使用双指针进行求解。

首先，将两个链表的长度分别记为a和b，公共部分的长度记为c。那么从表头走到公共节点的距离就是(a - c)和(b - c) 。

此时，记录两个指针A和B分别从链表的表头出发，走完当前链表后再走另一个链表，直到公共节点。可以得出下面的公式：

a + (b - c) = b + (a - c)

此时分为两种情况：

• 如果c = 0 ，意味着两个链表没有公共尾部，此时A和B均指向null。
• 如果c > 0 ，意味着两个链表有公共尾部，此时A和B均指向第一个公共节点。

因此，不管有没有公共节点，最终只需返回A或者B即可。

双指针

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getIntersectionNode = function(headA, headB) {
    let A = headA;
    let B = headB;
    while(A !== B) {
        A = A !== null ? A.next : headB;
        B = B !== null ? B.next : headA;
    }
    return A;
};

• 「时间复杂度 O(m + n)」。
• 「空间复杂度 O(1)」。

分析：

首先，声明两个变量分别指向两个链表的头部节点。按照上面的分析，A === B 有两种情况，一种是都指向null；一种是都指向第一个公共节点。

循环内部，指针先遍历完当前链表，然后遍历另一个链表，直到相遇或者为null 。遍历结束后，直接返回A或者B即可。因为此时A或者B指向的就是第一个公共节点或者null。

复杂度方面，最坏情况下，需要遍历完两个链表，因此时间复杂度是O(m + n) ；节点指针 A , B 使用常数大小的额外空间，因此空间复杂度是O(1) 。

总结

本题巧妙的使用遍历链表的方式获取第一个公共节点。遇到链表问题，首先需要想到双指针解法，需要牢记在心。

参考资料

[1]力扣题目链接: https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/oe5os3/