Link to LeetCode Problem

S1: 暴力法

对链表 A 的每个节点，都去链表 B 中遍历一遍找看看有没有相同的节点。

/**
 * 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) {
    if (!headA || !headB) return null;

    let pA = headA;
    while (pA) {
        let pB = headB;

        while (pB) {
            if (pA === pB) return pA;
            pB = pB.next;
        }

        pA = pA.next;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (headA == NULL || headB == NULL) return NULL;

        ListNode *pA = headA;

        while (pA != NULL) {
            ListNode *pB = headB;
            while (pB != NULL) {
                if (pA == pB) {
                    return pA;
                }
                pB = pB->next;
            }
            pA = pA->next;
        }
        return NULL;
    }
};

• Time: $O(m*n)$，m 和 n 分别是两个链表的长度。
• Space: $O(1)$

S2: 哈希表

• 先遍历遍历链表 A，将所有节点都存在一个哈希表中
• 再遍历链表 B，找到在哈希表中出现过的节点即为两个链表的交点。

/**
 * 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) {
    if (!headA || !headB) return null;

    const hashmap = new Map();

    let pA = headA;
    while (pA) {
        hashmap.set(pA, 1);
        pA = pA.next;
    }

    let pB = headB;
    while (pB) {
        if (hashmap.has(pB)) return pB;
        pB = pB.next;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        unordered_set<ListNode*> visited;
        ListNode* p = headA;
        while (p != NULL) {
            visited.insert(p);
            p = p->next;
        }
        p = headB;
        while (p != NULL) {
            if (visited.find(p) != visited.end()) return *visited.find(p);
            p = p->next;
        }
        return NULL;
    }
};

• Time: $O(m+n)$，m 和 n 分别是两个链表的长度。
• Space: $O(m)$

S3: 双指针

https://camo.githubusercontent.com/c1fabf4badffd96c0857bdc66bf8ccdf9214991b45c0e1b08c54feda9d91a77e/68747470733a2f2f63646e2e6a7364656c6976722e6e65742f67682f7375756b69692f39312d646179732d616c676f726974686d2f6173736574732f696e74657273656374696f6e5f6f665f6c696e6b65645f6c697374732e706e67

如果两个链表有交点的话：

https://camo.githubusercontent.com/3580f2f8d58e14290c175c9a117219b37d85e71c1d2b058a65b9982b10555f40/68747470733a2f2f63646e2e6a7364656c6976722e6e65742f67682f7375756b69692f39312d646179732d616c676f726974686d2f6173736574732f696e74657273656374696f6e5f6f665f6c696e6b65645f6c697374735f312e706e67

如果链表没有交点的话：