算法练习7：求两个单链表的相交点

两个单链表，相交，会成为一个横躺的Y形状，求它们的交点

// 初始化链表：
// node1: 1 -> 2 -> 3 -> 4
//                          -> 5
// node2: 6 -> 7 ------> 4

// 链表节点
function LinkNode(val) {
  this.val = val;
  this.next = null;
}

const node1 = new LinkNode(1)
const node2= new LinkNode(2)
const node3 = new LinkNode(3)
const node4 = new LinkNode(4)
const node5 = new LinkNode(5)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5

const node6 = new LinkNode(6)
const node7 = new LinkNode(7)
node6.next = node7
node7.next = node4

暴力解法

双层遍历，查看一个链表里是否有与另一个链表相同的节点地址，有的话，这个点就是它们相交点;

• 时间复杂度：O(n^2)
• 空间复杂度：O(1)

function getSameNode(node1, node2) {
  let p1 = node1;
  let p2 = node2;
  while(p1) {
    p2 = node2;
    while(p2) {
      if(p2.next === p1) {
        return p1
      }
      p2 = p2.next
    }
    p1 = p1.next
  }
  return null;
}

console.log(getSameNode(node1, node6)); // LinkNode { val: 4, next: LinkNode { val: 5, next: null } }

使用hash表

使用hash表来存储任意一个链表所有的节点地址，然后在遍历另一个链表，如果其某个节点在hash表中，这个点就是它们的相交点

• 时间复杂度：O(n+m)，约为O(n)
• 空间复杂度：O(n)

function getSameNode2(node1, node2) {
  let map = new Map()
  while(node1) {
    map.set(node1, 1)
    node1 = node1.next
  }
  while(node2) {
    if(map.has(node2)) {
      return node2;
    }else {
      node2 = node2.next
    }
  }
  return null;
}

console.log(getSameNode2(node1, node6)); // LinkNode { val: 4, next: LinkNode { val: 5, next: null } }

利用链表长度差k

先遍历2个链表node1、node2，分别获取2个链表的长度，假设node1长度较大，计算两个链表的差距k，然后遍历长链表，到第k位后，长短链表此时和短链表后面的长度一致了，此时继续同时遍历长链表和短链表，当它们的节点相同时，就是它们的相交点

• 时间复杂度：O(2n+m), 约为O(n)
• 空间复杂度：常量级，O(1)

function getSameNode3(node1, node2) {
  let len1 = 0;
  let len2 = 0;
  let p1 = node1; // p1指针，初始指向链表1的头节点
  let p2 = node2; // p2指针，初始指向链表2的头节点
  let k;
  // 计算链表1的长度
  while(p1) {
    len1 ++;
    p1 = p1.next
  }
  // 计算链表2的长度
  while(p2) {
    len2++;
    p2 = p2.next
  }
  // 计算两链表的长度差k，p1改指向长链表的头节点，p2改指向短链表的头节点
  if(len1 >= len2) {
    k = len1 - len2;
    p1 = node1
    p2 = node2
  }else {
    k = len2 - len1;
    p1 = node2;
    p2 = node1;
  }
  // 遍历长链表
  while(p1) {
    // 长链表先单独移动k位
    if(k !== 0) {
      k--;
      p1 = p1.next;
      // 移到k位后，两链接指针开始同时移动，查找相同节点
    }else {
      if(p1 !== p2) {
        p1 = p1.next
        p2 = p2.next
      }else {
        return p1;
      }
    }
  }
  return null;
}

console.log(getSameNode3(node1, node6)); // LinkNode { val: 4, next: LinkNode { val: 5, next: null } }