
# Intersection of Two Linked Lists

## Description

[doc](https://leetcode.com/problems/intersection-of-two-linked-lists/)

## Solutions

### First Idea

```javascript
/**
 * 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 curA = headA

  while (curA) {
    let curB = headB

    while (curB) {
      if (Object.is(curA, curB)) {
        return curA
      }

      curB = curB.next
    }

    curA = curA.next
  }

  return null
}
```

- Time Complexity: O(n^2)
- Space Complexity: O(1)

### Hash Version

```javascript
/**
 * 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) {
  const nodesOfB = new WeakSet()
  let cur = headB

  while (cur) {
    nodesOfB.add(cur)
    cur = cur.next
  }

  cur = headA
  while (cur) {
    if (nodesOfB.has(cur)) {
      return cur
    }

    cur = cur.next
  }

  return null
}
```

- Time Complexity: O(n)
- Space Complexity: O(n)
