【Day 10 】2024-04-17 - 160. 相交链表

[azl397985856]

160. 相交链表

入选理由

暂无

题目地址

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

前置知识

• 链表
• 双指针

  题目描述

  
  给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

图示两个链表在节点 c1 开始相交：

![](https://p.ipic.vip/bkdl1z.jpg)

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

 

示例 1：

![](https://p.ipic.vip/bzw15z.jpg)

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3 输出：Intersected at '8' 解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。 从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。 在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。 示例 2：

![](https://p.ipic.vip/26cojo.jpg)

输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1 输出：Intersected at '2' 解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。 从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。 在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。 示例 3：

![](https://p.ipic.vip/2tpyar.jpg)

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2 输出：null 解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。 由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。 这两个链表不相交，因此返回 null 。  

提示：

listA 中节点数目为 m listB 中节点数目为 n 0 <= m, n <= 3 * 104 1 <= Node.val <= 105 0 <= skipA <= m 0 <= skipB <= n 如果 listA 和 listB 没有交点，intersectVal 为 0 如果 listA 和 listB 有交点，intersectVal == listA[skipA + 1] == listB[skipB + 1]  

进阶：你能否设计一个时间复杂度 O(n) 、仅用 O(1) 内存的解决方案？

[rao-qianlin]

思路：使用双指针

public 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){
            if(pa == null){
                pa = headB;
            }
            else{
                pa = pa.next;
            }
            if(pb == null){
                pb = headA;
            }
            else{
                pb = pb.next;
            }
        }
        return pa;

    }
}

[zhiyuanpeng]

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        set_a = set()
        p_a = headA
        while p_a:
            set_a.add(p_a)
            p_a = p_a.next
        p_b = headB
        while p_b:
            if p_b in set_a:
                return p_b
            p_b = p_b.next
        return None

Time O(N) Space O(N)

[lxy1108]

思路

先遍历list A并利用hashmap存储节点，再遍历list B并在遍历过程中检查当前节点是否在hashmap里，如果有则为交点，否则没有交点

python3代码

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        nodesa = set()
        pointera = headA
        while pointera:
            nodesa.add(pointera)
            pointera = pointera.next
        pointerb = headB
        while pointerb:
            if pointerb in nodesa:
                return pointerb
            pointerb = pointerb.next
        return None

复杂度分析

空间复杂度 O(N)，因为额外开辟了空间用来存储其中一个链表的节点 时间复杂度 O(N)，因为需要遍历链表

[atom-set]

思路

题目要求不允许对链表进行修改，可以借助哈希表数据结果

• step1: 先将链表 A 的数据都存到哈希表中
• step2: 遍历链表 B，判断是否出现过，出现过返回

• 代码

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getIntersectionNode = function (headA, headB) {
  const visited = new Set();
  let temp = headA;
  while (temp !== null) {
    visited.add(temp);
    temp = temp.next;
  }

  temp = headB;
  while (temp !== null) {
    if (visited.has(temp)) {
      return temp;
    }
    temp = temp.next;
  }
  return null;
};

复杂度分析

• 时间复杂度: O(N)
• 空间复杂度: O(N)

[xil324]

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getIntersectionNode = function(headA, headB) {
    let first = headA, second = headB;
    while(first !== second) {
       first !== null ? first = first.next : first = headB;
       second !== null ? second = second.next: second = headA;
    }
    return first;
}; 

[xy147]

js代码

let getIntersectionNode = (headA,headB)=>{
    let pA = headA,pB = headB
    if(pA === null || pB === null){
        return null
    }
    while(pA != pB){
        pA = pA?pA.next:headB
        pB = pB?pB.next:headA
    }
    return pA
}

复杂度分析

• 时间复杂度: O(N)
• 空间复杂度: O(1)

[wwz223]

思路

先循环headA，把链表1的所有节点保存起来，然后遍历链表2，找到相同的节点，返回该节点的next

代码

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getIntersectionNode = function (headA, headB) {
    const visited = new Set();
    let temp = headA;
    while (temp !== null) {
        visited.add(temp);
        temp = temp.next;
    }
    temp = headB;

    while (temp !== null) {
        if (visited.has(temp)) {
            return temp;
        }
        temp = temp.next;
    }

    return null
};

复杂度分析

• 时间复杂度: O(m + n)
• 空间复杂度: O(1)

[YANGLimbo]

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        // 方法1：暴力，对于每一个list A的节点，遍历list B 并比较 过程略

        // 自己想的：计算链表，长度相减，长的那个先走差值步数，然后一起走，比对。灵感来源昨天遇到的快慢指针

        ListNode* ptrA = headA;
        ListNode* ptrB = headB;

        // 已知链表A B均不为空 m为链表A长度，n为链表B长度
        int m = 1, n = 1; 

        while(ptrA->next!=nullptr){
            ptrA = ptrA->next;
            m++;
        }
        while(ptrB->next!=nullptr){
            ptrB = ptrB->next;
            n++;
        }

        // 使用快慢指针，链表长的那一方先走abs(m-n)步
        int distance = abs(m-n);
        ptrA =headA;
        ptrB = headB;
        if(m>n){
            while(distance>0){
                ptrA = ptrA->next;
                distance--;
            }
        }else{
            while(distance>0){
                ptrB = ptrB->next;
                distance--;
            }
        }

        if(ptrA == ptrB){
            return ptrA;// 相同的链表
        }
        ListNode* ans = nullptr;
        while(ptrA->next!=nullptr){
            if(ptrA->next == ptrB->next){
                ans = ptrA->next;
                break;
            }
            ptrA = ptrA->next;
            ptrB = ptrB->next;
        }
        return ans;
    }
};

[coderXiaowq]

Java 时间复杂度O(n)

public class Solution {
    public ListNode getIntersectionNode(ListNode A, ListNode B) {
        ListNode p1 = new ListNode(1);
        ListNode p2 = new ListNode(1);
        p1.next = A;
        p2.next = B;
        Map<ListNode,Integer> map = new HashMap<>();
        while(p1.next != null){
            map.put(p1.next,0);
            p1=p1.next;
        }
        while(p2.next!=null){
            if(map.containsKey(p2.next))
                return p2.next;
            p2=p2.next;
        }
        return null;
    }
}

[CathyShang]

思路 讲义原题 双指针 cur1，cur2

• cur1，cur2分布从headA，headB开始遍历，当其中一个为nullptr时，指向另一个链表头再遍历；
• 若有交点，则cur1与cur2会在交点相遇 假设，headA非交点长度为L1，headB非交点长度为L2，交点之后链表长度L3，指针相遇时，cur1，cur2走过的链表长度分别为L1+L3+L2,L2+L3+L1, 验证了它们会相遇。

代码

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* cur1 = headA;
        ListNode* cur2 = headB;
        int flag1 = 0,flag2 = 0;
        while(cur1!=nullptr || cur2!=nullptr){
            if(cur1==nullptr){
                cur1 = headB;
                flag1 += 1;
            }
            if(cur2==nullptr){
                cur2 = headA;
                flag2 += 1;
            }
            if(cur1 == cur2){break;} // 表示指向同一节点，指针相等（不是值相等）
            if(flag1==2||flag2==2){break;} //当没有交点时避免死循环
            std::cout << cur1->val << endl;
            cur1 = cur1->next;
            cur2 = cur2->next;
        }
        return cur1;
    }
};

复杂度

• 时间 $O(M+N)$ 最坏情况没有交点，两个链表长度分布M,N
• 空间 $O(1)$ 双指针

[GReyQT]

题解思路：

1，遍历链表headA将每个节点的地址存入数组中 2，遍历链表headB，当headB中节点与A中的相等时返回，或者为找到既不相交返回空 代码：

/**
 * 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) {
        vector<ListNode *> headAvec;
        while(headA != nullptr)
        {
            headAvec.push_back(headA);
            headA = headA->next;
        }
        while(headB != nullptr)
        {
            for(auto it = headAvec.begin(); it != headAvec.end(); ++it)
            {
                if(*it == headB)
                {
                    return headB;
                }
            }
            headB = headB->next;
        }
        return headB;
    }
};

复杂度分析：

• 时间复杂度：取决于链表的长度n，时间的复杂度为O(n^2)
• 空间复杂度：取决于链表的长度n，空间复杂度为 O( n)

[JackinAI]

思路：

计算两个链表的长度：首先遍历两个链表，计算它们的长度 m 和 n。 对齐两个链表的起始位置：根据长度之差，移动较长链表的指针 diff = |m - n| 步，这样可以使得两个链表的尾部对齐。 遍历链表寻找相交节点：然后从两个链表的当前位置开始，每次同时移动两个指针一步，如果两个指针指向了同一个节点，那么这个节点就是相交的起始节点。 返回结果：如果遍历过程中没有找到相交的节点，那么返回 null。 代码： ` function getIntersectionNode(headA, headB): if headA == null or headB == null: return null

# Step 1: Calculate the lengths of the two lists
lenA, lenB = 0, 0
currentA, currentB = headA, headB
while currentA != null:
    lenA += 1
    currentA = currentA.next
while currentB != null:
    lenB += 1
    currentB = currentB.next

# Step 2: Align the starting positions of the two lists
currentA, currentB = headA, headB
if lenA > lenB:
    for i in range(lenA - lenB):
        currentA = currentA.next
else:
    for i in range(lenB - lenA):
        currentB = currentB.next

# Step 3: Traverse the lists to find the intersection node
while currentA != null and currentB != null:
    if currentA == currentB:
        return currentA
    currentA = currentA.next
    currentB = currentB.next

# Step 4: If no intersection is found, return null
return null

` 复杂度：时间复杂度是 O(m + n)，因为我们需要遍历两个链表来找到相交节点。由于 m 和 n 分别是链表 A 和 B 的长度，所以这个算法的时间复杂度可以简化为 O(m + n)。由于我们只使用了一个额外的指针来遍历链表，所以空间复杂度是 O(1)

[Junru281]

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        data = set()
        while headA:
            data.add(headA)
            headA = headA.next

        while headB:
            if headB in data:
                return headB
            else: headB = headB.next

[sanjiu81]

思路 双指针 代码 class Solution { public: ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode cur1 = headA; ListNode* cur2 = headB; int flag1 = 0,flag2 = 0; while(cur1!=nullptr || cur2!=nullptr){ if(cur1==nullptr){ cur1 = headB; flag1 += 1; } if(cur2==nullptr){ cur2 = headA; flag2 += 1; } if(cur1 == cur2){break;} if(flag1==2||flag2==2){break;} std::cout << cur1->val << endl; cur1 = cur1->next; cur2 = cur2->next; } return cur1; } }; 复杂度 时间O(M+N） 空间O(N)

[Dtjk]

class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *ptr1 = headA;
ListNode *ptr2 = headB;

    while(ptr1 != ptr2){
        ptr1 = ptr1->next;
        ptr2 = ptr2->next;

        if(ptr1 == ptr2) break;

        if(ptr1 == NULL) ptr1 = headB;
        if(ptr2 == NULL) ptr2 = headA;

    }
    return ptr1;
}
};

[Martina001]

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 把A和B接到一起 让两个指针分别走A-B 和B-A，如果有相遇 就是有交点 如果没有交点，此时两个指针都走到末尾为null
        ListNode aNode = headA;
        ListNode bNode = headB;
        while(aNode != bNode){
            if(aNode == null){
                aNode = headB;
            }else{
                aNode = aNode.next;
            }

            if(bNode == null){
                bNode = headA;
            }else{
                bNode = bNode.next;
            }
        }
        return aNode;
    }
}

[pandapls]

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
示例 2：

输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
示例 3：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。

提示：

listA 中节点数目为 m
listB 中节点数目为 n
0 <= m, n <= 3 * 104
1 <= Node.val <= 105
0 <= skipA <= m
0 <= skipB <= n
如果 listA 和 listB 没有交点，intersectVal 为 0
如果 listA 和 listB 有交点，intersectVal == listA[skipA + 1] == listB[skipB + 1]

进阶：你能否设计一个时间复杂度 O(n) 、仅用 O(1) 内存的解决方案？

思路

使用Set存储节点 判断是否存在该链表节点

代码

var getIntersectionNode = function(headA, headB) {
    let set = new Set()
    let tmp = headA;
    while(tmp) {
        set.add(tmp)
        tmp = tmp.next
    }
    tmp = headB;
    while(tmp) {
        if (set.has(tmp)) {
            return tmp
        }

        tmp = tmp.next
    }

    return null
};

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(n)