160.相交链表

https://leetcode-cn.com/problems/intersection-of-two-linked-lists

• 160.相交链表

  • 题目描述

  • 方法 1：暴力法

    • 思路

    • 复杂度

    • 代码(JavaScript/C++)

  • 方法 2：哈希表

    • 思路

    • 复杂度

    • 代码(JavaScript/C++)

  • 方法 3：双指针

    • 思路

    • 复杂度

    • 代码(JavaScript/C++)

题目描述

编写一个程序，找到两个单链表相交的起始节点。

https://leetcode-cn.com/problems/intersection-of-two-linked-lists

方法 1：暴力法

思路

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

复杂度

• 时间复杂度：$O(M * N)$, M, N 分别为两个链表的长度。

• 空间复杂度：$O(1)$。

代码(JavaScript/C++)

JavaScript Code

/**
 * 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;
    }
};

C++ Code

/**
 * 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;
    }
};

方法 2：哈希表

思路

• 先遍历一遍链表 A，用哈希表把每个节点都记录下来(注意要存节点引用而不是节点值)。

• 再去遍历链表 B，找到在哈希表中出现过的节点即为两个链表的交点。

复杂度

• 时间复杂度：$O(M + N)$, M, N 分别为两个链表的长度。

• 空间复杂度：$O(N)$，N 为链表 A 的长度。

代码(JavaScript/C++)

JavaScript Code

/**
 * 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;
    }
};

C++ Code

/**
 * 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;

        map<ListNode*, bool> seen;
        while (headA) {
            seen.insert(pair<ListNode*, bool>(headA, true));
            headA = headA->next;
        }
        while (headB) {
            if (seen.find(headB) != seen.end()) return headB;
            headB = headB->next;
        }
        return NULL;
    }
};

方法 3：双指针

思路

如果链表有交点

如果链表没有交点

1. 两个链表长度一样，第一次遍历结束后 pA 和 pB 都是 null，结束遍历

2. 两个链表长度不一样，两次遍历结束后 pA 和 pB 都是 null，结束遍历

复杂度

• 时间复杂度：$O(M + N)$, M, N 分别为两个链表的长度。

• 空间复杂度：$O(1)$。

代码(JavaScript/C++)

/**
 * 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,
        pB = headB;
    while (pA !== pB) {
        pA = pA === null ? headB : pA.next;
        pB = pB === null ? headA : pB.next;
    }
    return pA;
};

C++ Code

/**
 * 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;
        ListNode* pB = headB;
        while (pA != pB) {
            pA = pA == NULL ? headB : pA->next;
            pB = pB == NULL ? headA : pB->next;
        }

        return pA;
    }
};

更多题解可以访问：https://github.com/suukii/91-days-algorithm