题目描述

解题思路

思路一：前后双指针（数节点）

前后双指针其实指的是一个指针先走 n 步，另一个指针再与前一个指针以相同的速度走。用到这个思路的还有学算法刷LeetCode【剑指offer专题】：22. 链表中倒数第k个节点。

这道题是找到两个链表的第一个公共节点，找不到则返回 null。

先算出两个链表的长度，然后比较两个链表的长度，并算出两个链表的差，即长的链表比短的链表需要先走 delta 步。
两个链表一起走，如果遇到相等的节点则返回，否则返回 null

完整代码


/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
const getNodeNumber = (head) => {
    let count = 0;
    while(head){
        head = head.next;
        count ++;
    }
    return count;
}

var getIntersectionNode = function(headA, headB) {
    // 先分别计算两个链表的长度，并求出 delta
    let countA = getNodeNumber(headA)
    let countB = getNodeNumber(headB)
    let shorter =  countA > countB ? headB : headA
    let longer = countA > countB ? headA : headB

    let delta = Math.abs(countA - countB )

    // longer 先走差的步数
    let node1 = longer
    for(let i = 0; i < delta; i++){
        node1 = node1.next;
    }

    // 遍历两个链表，如果相遇，则为第一个公共节点。
    let node2 = shorter;
    while(node1 != node2){
        node1 = node1.next;
        node2 = node2.next;
    }

    return node1
};

复制代码

复杂度分析

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

两个链表分别遍历两次，第 1 次得到两个链表的节点数，第二次找到两个链表的第一个公共节点。

空间复杂度： O(1)

不需要的保存链表的节点。

思路二：栈

栈的特点就是先进后出，这时候把两个链表变成两个栈，此时在栈的顶部就是两个链表的尾部，根据这个题目，从链表的额尾部向前查找才能找到第一个公共节点，所以我们让这两个栈的元素同时出栈，并比较节点是否相等，遇到不相等的节点说明刚刚过了第一个公共节点，返回这个公共节点即可。

将两个链表入栈
将两个栈的元素同时出栈，并将相同节点更新，遇到不相同的节点则退出循环，将相同的节点返回即可。

完整代码


/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */

var getIntersectionNode = function(headA, headB) {
    // 构建两个栈
    let stack1 = [];
    let stack2 = [];
    let node1 = headA;
    while(node1){
        stack1.push(node1)
        node1 = node1.next;
    }
    let node2 = headB;
    while(node2){
        stack2.push(node2)
        node2 = node2.next;
    }
    
    // 两个栈的节点同时出栈并比较，同时更新最后一个相同的节点，遇到不同的节点则跳出循环。
    let firstCommonNode = null;
    while(stack1.length && stack2.length){
        const cur1 = stack1.pop();
        const cur2 = stack2.pop();
        if(cur1 !== cur2){
            break;
        }
        firstCommonNode = cur1; 
    }

    return firstCommonNode
};

复制代码