当前位置:   article > 正文

LeetCode160:相交链表_给你两个单链表的头节点 heada 和 headb ,请你找出并返回两个单链表相交的起始节

给你两个单链表的头节点 heada 和 headb ,请你找出并返回两个单链表相交的起始节

1、要求

给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。
图示两个链表在节点 c1 开始相交:
在这里插入图片描述
题目数据 保证 整个链式结构中不存在环。
注意,函数返回结果后,链表必须 保持其原始结构 。

自定义评测:
评测系统 的输入如下(你设计的程序 不适用 此输入):
intersectVal - 相交的起始节点的值。如果不存在相交节点,这一值为 0 listA - 第一个链表 listB - 第二个链表
skipA - 在 listA 中(从头节点开始)跳到交叉节点的节点数 skipB - 在 listB
中(从头节点开始)跳到交叉节点的节点数 评测系统将根据这些输入创建链式数据结构,并将两个头节点 headA 和 headB
传递给你的程序。如果程序能够正确返回相交节点,那么你的解决方案将被 视作正确答案。

2、示例

输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出:Intersected at ‘8’
解释:相交节点的值为 8 (注意,如果两个链表相交则不能为 0)。 从各自的表头开始算起,链表 A 为 [4,1,8,4,5],链表 B 为
[5,6,1,8,4,5]。 在 A 中,相交节点前有 2 个节点;在 B 中,相交节点前有 3 个节点。 — 请注意相交节点的值不为
1,因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点)
是不同的节点。换句话说,它们在内存中指向两个不同的位置,而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点,B 中第四个节点)
在内存中指向相同的位置。

前置条件,如果在自己的工具中测试时,需要创建ListNode类

public class ListNode {
    public int val;
    public ListNode next;

    public ListNode(int x){
        val=x;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

3、题目解析

先解析一下题目的意思吧,如果把题目解析明白了,这个题本身并不难,但由于官方解释的有点懵;
这里的相交的意思是值和位置都得相同。所以类似于=== 和 ==的区别:一个要求值和类型都等;一个只要求值相等就行;
下面的是一个大佬发表的评论,我借鉴来了,当时看完就懂了

pA走过的路径为A链+B链
pB走过的路径为B链+A链
pA和pB走过的长度都相同,都是A链和B链的长度之和,相当于将两条链从尾端对齐,如果相交,则会提前在相交点相遇,如果没有相交点,则会在最后相遇。
pA:1->2->3->4->5->6->null->9->5->6->null
pB:9->5->6->null->1->2->3->4->5->6->null

4、解题思路

方法一:HashSet集合

判断两个链表是否相交,可以使用HashSet进行存储判断;
首先遍历链表A,然后将链表A中的结点加入到哈希集合中,然后遍历链表B,对于遍历到的每个节点,判断是否在哈希集合中:

  • 如果当前节点不在哈希,则遍历下一个节点
  • 如果当前节点在哈希中,后面的结点都在哈希集合中,即从当前节点开始的所有节点都在两个链表的相交部分,因此在链表B中遍历到的第一个哈希集合中的节点就是两个链表相交的地方,返回该节点;

如果链表B中所有节点都不在哈希集合中,则两个链表都不相交返回null。

public class LeetCode160 {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //创建HashSet集合
        HashSet<ListNode> listNodes = new HashSet<>();
        //如果链表A不为空,则添加到创建的哈希集合中
        while (headA != null){
            listNodes.add(headA);
            headA = headA.next;
        }
        //遍历链表B,对比哈希集合,如果链表B中的值在哈希集合找不到,则返回null
        while (headB != null){
            if (listNodes.contains(headB)){
                return headB;
            }
            headB = headB.next;
        }
        return null;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

时间复杂度:O(m+n),两个链表各遍历一次
空间复杂度:O(m),需要借用哈希集合存储链表A

方法二:双指针

只有当链表 A 和 B 都不为空时,两个链表才可能相交。
首先判断链表 A 和 B 是否为空,如果其中至少有一个链表为空,则两个链表一定不相交,返回 null。
如果两个两个链表都不为空,在进行以下判断:

  • 如果指针A不为空时,则指向下一个节点;如果指针B不为空时,则指向下一个节点;
  • 如果指针A为null时,则将指针A指向链表B的头节点,然后进行指向B的下一个节点;
  • 如果指针B为null时,则将指针B指向链表A的头节点,然后进行指向A的下一个节点;
  • 直至A和B指针指向同一个节点或者都为空时,返回A和B指向的节点或者返回null
  • 如果能有相交的地方,在相交头一个节点位置,链表A和链表B到达末尾的距离是一样的
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    //双链表
    if (headA == null || headB == null){
        return null;
    }
    ListNode A = headA,B = headB;
    while (A != B){
        A = A == null ? headB : A.next;
        B = B == null ? headA : B.next;
    }
    return B;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

时间复杂度O(m+n),最差的情况是这样
空间复杂度O(1)

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/689893
推荐阅读
相关标签
  

闽ICP备14008679号