【力扣热题100】—— Day3.相交链表

news/2024/11/29 19:51:43/

被你改变的那部分我,代替你,永远与我站在一起

                                                                        —— 24.11.28

160. 相交链表

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

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

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

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

自定义评测:

评测系统 的输入如下(你设计的程序 不适用 此输入):

  • intersectVal - 相交的起始节点的值。如果不存在相交节点,这一值为 0
  • listA - 第一个链表
  • listB - 第二个链表
  • skipA - 在 listA 中(从头节点开始)跳到交叉节点的节点数
  • skipB - 在 listB 中(从头节点开始)跳到交叉节点的节点数

评测系统将根据这些输入创建链式数据结构,并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点,那么你的解决方案将被 视作正确答案 。

 

示例 1:

输入: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 中第四个节点) 在内存中指向相同的位置。

示例 2:

输入:intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出:Intersected at '2'
解释:相交节点的值为 2 (注意,如果两个链表相交则不能为 0)。
从各自的表头开始算起,链表 A 为 [1,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
输出:No intersection
解释:从各自的表头开始算起,链表 A 为 [2,6,4],链表 B 为 [1,5]。
由于这两个链表不相交,所以 intersectVal 必须为 0,而 skipA 和 skipB 可以是任意值。
这两个链表不相交,因此返回 null 。 

提示:

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

方法一:暴力遍历

类似于冒泡循环,对于每一个元素都整体遍历一遍另一个链表,看两者中是否有节点相同,如果有节点相等,就退出循环,如果没有,则将所有元素遍历比较结束后,退出循环,返回null值

Java实现:

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode p = headA;ListNode q = headB;for(p = headA; p != null; p = p.next){for(q = headB; q != null; q = q.next){if(p == q){return p;}}}return null;}
}


方法二:存入容器后直接查询

Java实现

将其中一个链表中的所有节点都存入哈希表中,然后遍历第二个链表,调用contains方法,看第一个链表存入的哈希表中是否含有第二个链表中的某一节点,由于是从头到尾遍历,所以在遍历第二个链表过程中第一个判断包含的节点就是二者首次相交的节点,进行返回即可

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {Set<ListNode> s = new HashSet<>();for (ListNode p = headA; p != null; p = p.next) {s.add(p);}for (ListNode p = headB; p != null; p = p.next) {if (s.contains(p))return p;}return null;}
}


Python实现

遍历链表A,并将其节点存入集合

遍历B的每个节点并在集合中进行查询,一旦遍历过程中查询到相同节点,即说明有交点,否则无

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution:def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:A = set()cur1 = headAcur2 = headBwhile cur1:A.add(cur1)cur1 = cur1.nextwhile cur2:if cur2 in A:return cur2cur2 = cur2.nextreturn None


方法三: 双指针

先遍历其中一个链表,当到底末端后跳到另一链表,最后

若两链表没有公共结点,那么两个链表指针都会走过 s1+s2个结点,同时到达两链表末尾

若有公共结点,由于最后会同时走到两链表终点,所以倒退回去,两个指针一定会在第一个公共结点处相遇

当然,若两链表等长,那确实不会跳到另一链表,不过链表等长本身指针就是同步的,同样也能找到公共结点

初始化指针:

首先创建了两个指针和g,分别初始化为链表A的头节点headA和链表B的头节点headB。这两个指针将用于遍历两个链表
循环查找相交节点:
进入一个while循环,循环的条件是p和q不相等。在每次循环中,会对p和q进行移动操作。

对于指针p:

通过p=p== null?headB :p.next;这行代码来移动p指针。它的逻辑是,如果p指针当前指向的节点为null(意味着已经遍历完链表A),那么就将p重新指向链表B的头节点headB,开始遍历链表B;如果p当前指向的节点不为null,那么就将移动到下一个节点(即p.next)。

对于指针q:

类似地,通过g=g== null?headA :q.next;来移动g指针。也就是当q指针当前指向的节点为null(即已经遍历完链表B)时,将q重新指向链表A的头节点head,开始遍历链表A;若q当前指向的节点不为null,则将q移动到下一个节点(q.next)

返回结果:

当p和q相等时,循环结束。此时有两种情况:
如果p(和q)为null,说明两个链表没有相交节点,那么返回null符合预期。如果p(和g)不为null,则说明找到了相交节点,此时返回p(或者q,因为它们此时指向同一个节点),这个节点就是两个链表的相交节点。


Java实现

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode p = headA, q = headB;while (p != q) {p = p == null ? headB : p.next;q = q == null ? headA : q.next;}return p;}
}


Python实现

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution:def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:p = headAq = headBwhile p != q:p = p.next if p else headBq = q.next if q else headAreturn p


http://www.ppmy.cn/news/1550974.html

相关文章

连续变量的 交叉熵 如何计算 python tensorflow

连续变量的交叉熵通常在机器学习中的回归问题中使用&#xff0c;但它也可以用于分类问题&#xff0c;当概率分布是连续的时。连续变量的交叉熵计算公式如下&#xff1a; 设 \( p(x) \) 是真实概率密度函数&#xff0c;\( q(x) \) 是预测概率密度函数&#xff0c;交叉熵 \( H(p…

ELK配置索引清理策略

在ELFK&#xff08;Elasticsearch, Logstash,Filebeat, Kibana&#xff09;堆栈中配置索引清理策略是一个常见的需求&#xff0c;因为日志数据会随着时间的推移而积累&#xff0c;占用大量的存储空间。以下是一些配置索引清理策略的方法&#xff1a; 1. 使用索引生命周期管理&…

Linux操作系统2-进程控制3(进程替换,exec相关函数和系统调用)

上篇文章&#xff1a;Linux操作系统2-进程控制2(进程等待&#xff0c;waitpid系统调用&#xff0c;阻塞与非阻塞等待)-CSDN博客 本篇代码Gitee仓库&#xff1a;Linux操作系统-进程的程序替换学习 d0f7bb4 橘子真甜/linux学习 - Gitee.com 本篇重点&#xff1a;进程替换 目录 …

第二节——计算机网络(四)物理层

车载以太网采用差分双绞线车载以太网并未指定特定的连接器&#xff0c;连接方式更为灵活小巧&#xff0c;能够大大减轻线束重量。传统以太网一般使用RJ45连接器连接。车载以太网物理层需满足车载环境下更为严格的EMC要求&#xff0c;100BASE-T1\1000BASE-T1对于非屏蔽双绞线的传…

如何在Python中进行数学建模?

数学建模是数据科学中使用的强大工具&#xff0c;通过数学方程和算法来表示真实世界的系统和现象。Python拥有丰富的库生态系统&#xff0c;为开发和实现数学模型提供了一个很好的平台。本文将指导您完成Python中的数学建模过程&#xff0c;重点关注数据科学中的应用。 数学建…

MemVerge与美光科技利用CXL®内存提升NVIDIA GPU利用率

该联合解决方案将 GPU 利用率提高了 77%&#xff0c;并将 OPT-66B 批量推理的速度提高了一倍以上。 2023 年 3 月 18 日&#xff0c;作为大内存软件领域领导者的 MemVerge&#xff0c;与美光科技联手推出了一项突破性解决方案&#xff0c;该方案通过智能分层的 CXL 内存&#x…

《Python语言程序设计》(2018年版)第15遍刷第1章第1题和第2题

2024.11.28 重新开始刷题 第一章 1.1 print( Welcome to Python Welcome to Computer Science Programming is fun )1.2 text_message "Welcome to Python\n"print(text_message * 5)

蓝桥杯每日真题 - 第24天

题目&#xff1a;&#xff08;货物摆放&#xff09; 题目描述&#xff08;12届 C&C B组D题&#xff09; 解题思路&#xff1a; 这道题的核心是求因数以及枚举验证。具体步骤如下&#xff1a; 因数分解&#xff1a; 通过逐一尝试小于等于的数&#xff0c;找到 n 的所有因数…