36-两个链表的第一个公共结点-快慢指针

题目描述

输入两个链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）

解法 1: 遍历+哈希表记录

比较容易想到的思路：

开辟哈希表 map。key 是节点，value 是 boolean，代表节点是否出现过
对 list1 进行遍历，设置 map[节点]=true
对 list2 进行遍历，如果节点在 map 中出现过，那么说明这是两个链表的公共节点，返回

代码：

var getIntersectionNode = function(headA, headB) {
    const map = new Map();
    let node = headA;
    while (node) {
        map.set(node, true);
        node = node.next;
    }

    node = headB;
    while (node) {
        if (map.has(node)) return node;
        node = node.next;
    }
    return null;
};

时间复杂度是O(N)，空间复杂度是O(N)。

解法二

题目提示了，空间复杂度可以降低到O(1)。这时候不能用哈希表，可以使用快慢指针的思路来处理。整体思路如下：

遍历得到两个链表的长度，以及长度差 diff
将慢指针 slow 指向较长链表，快指针 fast 指向较短链表
slow 向前移动 diff 个距离
slow 和 fast 同时向前移动，每次移动一个距离。若存在公共节点，那么它们一定会遇上。

代码：

/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function FindFirstCommonNode(pHead1, pHead2)
{
   let node = pHead1;
   let len1 = 0;
   while(node){
        len1++;
        node = node.next;
   }
   if(!len1) return null;
   node = pHead2;
   let len2 = 0;
   while(node){
        len2++;
        node = node.next;
   }
   if(!len2) return null; 
   let diff,slow,fast;
   if(len1>len2){
        diff = len1-len2;
        slow = pHead1;
        fast = pHead2;
   }else{
        diff = len2-len1;
        slow = pHead2;
        fast = pHead1;
   }
   while(diff){
       slow = slow.next;
       diff--;
   }
   while(slow != fast){
    slow = slow.next;
    fast = fast.next;
    }
    return slow;
   
}

时间复杂度是O(N)，空间复杂度是O(1)。