160.相交链表

链接：160.相交链表
难度：Easy
标签：哈希表、链表、双指针
简介：给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

题解 1 - typescript

• 编辑时间：2021-06-04
• 执行用时：128ms
• 内存消耗：46.9MB
• 编程语言：typescript
• 解法介绍：利用 set 储存。

function getIntersectionNode(headA: ListNode | null, headB: ListNode | null): ListNode | null {
  if (headA === null || headB === null) return null;
  const setA = new Set<ListNode>();
  const setB = new Set<ListNode>();
  let pA: ListNode | null = headA;
  let pB: ListNode | null = headB;
  while (pA !== null && pB !== null) {
    setA.add(pA);
    setB.add(pB);
    if (setB.has(pA)) return pA;
    if (setA.has(pB)) return pB;
    pA = pA.next;
    pB = pB.next;
  }
  while (pA !== null) {
    if (setB.has(pA)) return pA;
    pA = pA.next;
  }
  while (pB !== null) {
    if (setA.has(pB)) return pB;
    pB = pB.next;
  }
  return null;
}

题解 2 - c

• 编辑时间：2021-11-19
• 执行用时：36ms
• 内存消耗：13.5MB
• 编程语言：c
• 解法介绍：双指针。

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode *a = headA, *b = headB;
    while(a != b){
        a = a ? a->next : headB;
        b = b ? b->next : headA;
    }
    return a;
}

题解 3 - c

• 编辑时间：2021-11-19
• 执行用时：36ms
• 内存消耗：13.5MB
• 编程语言：c
• 解法介绍：双指针。

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode *a = headA, *b = headB;
    while(a != b){
        a = a ? a->next : headB;
        b = b ? b->next : headA;
    }
    return a;
}