Skip to content

Latest commit

 

History

History
260 lines (209 loc) · 5.56 KB

10.intersection-of-two-linked-lists.md

File metadata and controls

260 lines (209 loc) · 5.56 KB
Raw

160.相交链表

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

题目描述

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

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