leetcode 160 相交链表

leetcode 160 相交链表

题目要求

给定两个单链表的头节点 `headA` 和 `headB` ，找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回null。并且题目保证链表不存在环

第一种解法

思路

最直观的思路，通过一个set集合，遍历A链表，将所有节点存入，然后遍历B链表，如果找到一个节点存在于set，那么这就是他们的相交节点，return即可。

当然这种方式并不是最优解，他的时间复杂度符合题目要求O(n+m)，但是他的空间复杂度却达到了O(n),题目希望空间复杂度控制在O(1)

图解

这道题比较直观，就没必要画图了。

代码

function getIntersectionNode(
  headA: ListNode | null,
  headB: ListNode | null
): ListNode | null {
  let temp: ListNode = headA;
  let _set = new Set();
  while (temp) {
    _set.add(temp);
    temp = temp.next;
  }
  temp = headB;
  while (temp) {
    if (_set.has(temp)) {
      return temp;
    } else {
      temp = temp.next;
    }
  }
  return null;
}

第二种解法

思路

通过双指针，不利用新的数据结构，这样空间复杂度就控制在了O(1)，但是考虑到两个链表长度不一样，如果都是同时往后面移动一位，这样永远都不可能相等，所以借助一个巧妙的技巧

刚开始n1指针指向headA，n2指针指向headB，两个指针只要不相等就同时往后面移动，直到其中一个指针指向null，那么这个时候继续往后走，null自然没有next的，所以我们将n1指向headB，同理n2指向null的时候，它的下一步也是指向headA。

我们将headA分成两个区域，方便我们理解这种技巧，headA分成与headB不相交的部分(**selectA**)和相交的部分(**notselectA**)，同样我们将headB分成与headA相交的部分(**selectB**)和不相交的部分(**notselectB**)。于是n1走了长度就是**selectA+notSelectA+selectB**,n1走了长度就是**selectB+notSelectB+selectA**

图解

测试用例listA = [4,1,8,4,5], listB = [5,6,1,8,4,5],

这时初始化后n1和n2的指向

经过循环，由于headA长度比较短，所以他先走到null，

这个时候将n1指向headB的头节点

代码

function getIntersectionNode(
  headA: ListNode | null,
  headB: ListNode | null
): ListNode | null {
  let n1: ListNode = headA;
  let n2: ListNode = headB;

  while (n1 !== n2) {
    if (n1) {
      n1 = n1.next;
    } else {
      n1 = headB;
    }

    if (n2) {
      n2 = n2.next;
    } else {
      n2 = headA;
    }
  }
  return n1;
}