六六力扣刷题链表之链表相交

简介: 六六力扣刷题链表之链表相交

前言

之前小六六一直觉得自己的算法比较菜,算是一个短板吧,以前刷题也还真是三天打鱼,两台晒网,刷几天,然后就慢慢的不坚持了,所以这次,借助平台的活动,打算慢慢的开始开刷,并且自己还会给刷的题总结下,谈谈自己的一些思考,和自己的思路等等,希望对小伙伴能有所帮助吧,也可以借此机会把自己短板补一补,希望自己能坚持下去呀

链表

题目

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

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

image.png

输入: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 个节点。

image.png

输入: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 个节点。

解析

按小六六来说,其实要判断2个链表是否相交,其实就是看这2个链表有咩有值相等多元素,其实方法还是蛮多的

哈希集合

判断两个链表是否相交,可以使用哈希集合存储链表节点。

  • 首先遍历链表 =headA,并将链表headA 中的每个节点加入哈希集合中。然后遍历链表headB,对于遍历到的每个节点,判断该节点是否在哈希集合中:
  • 如果当前节点不在哈希集合中,则继续遍历下一个节点;
  • 如果当前节点在哈希集合中,则后面的节点都在哈希集合中,即从当前节点开始的所有节点都在两个链表的相交部分,因此在链表 headB 中遍历到的第一个在哈希集合中的节点就是两个链表相交的节点,返回该节点。

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

package com.six.finger.leetcode.five;
import com.six.finger.leetcode.common.ListNode1;
import java.util.HashSet;
public class fourtytwo {
    public static void main(String[] args) {
        ListNode1 listNode1 = new ListNode1(8);
        ListNode1 listNode12=new ListNode1(4);
        ListNode1 listNode13=new ListNode1(8);
        listNode12.next=listNode13;
        ListNode1 intersectionNode = getIntersectionNode(listNode1, listNode12);
    }
    public static ListNode1 getIntersectionNode(ListNode1 headA, ListNode1 headB) {
        HashSet set = getSet(headA);
        while (headB != null) {
            if (set.contains(headB.val)){
                return headB;
            }
            headB=headB.next;
        }
        return null;
    }
    private static HashSet getSet(ListNode1 headA) {
        HashSet<Integer> set = new HashSet<>();
        while (headA != null) {
            set.add(headA.val);
            headA = headA.next;
        }
        return set;
    }
}

结束

哈哈,又是更文挑战,可以督促我刷题,感谢大家一起加油,题刷起来呀。我是小六六,三天打鱼,两天晒网!

相关文章
|
2天前
【数据结构OJ题】相交链表
力扣题目——相交链表
13 1
【数据结构OJ题】相交链表
|
20天前
|
Java
力扣经典150题第五十八题:合并两个有序链表
力扣经典150题第五十八题:合并两个有序链表
15 2
|
20天前
|
Java
力扣经典150题第六十题:反转链表 II
力扣经典150题第六十题:反转链表 II
11 1
|
20天前
|
存储 Java
力扣经典150题第五十九题: 随机链表的复制
力扣经典150题第五十九题: 随机链表的复制
13 1
|
9天前
|
存储 算法 C语言
刷题训练之链表
刷题训练之链表
10 0
|
20天前
|
Java 索引
力扣经典150题第五十六题:环形链表
力扣经典150题第五十六题:环形链表
11 0
|
1月前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
|
1月前
|
存储 SQL 算法
LeetCode 题目 86:分隔链表
LeetCode 题目 86:分隔链表
|
1月前
|
存储 算法 Java
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
14 2
|
2月前
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点.
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点
31 1