互联网行业信息网站,北京网站开发网络公司,网站域名怎么填写,自己怎么做网站卖东西#x1f4da;博客主页#xff1a;爱敲代码的小杨.
✨专栏#xff1a;《Java SE语法》
❤️感谢大家点赞#x1f44d;#x1f3fb;收藏⭐评论✍#x1f3fb;#xff0c;您的三连就是我持续更新的动力❤️
#x1f64f;小杨水平有限#xff0c;欢迎各位大佬指点…
博客主页爱敲代码的小杨.
✨专栏《Java SE语法》
❤️感谢大家点赞收藏⭐评论✍您的三连就是我持续更新的动力❤️
小杨水平有限欢迎各位大佬指点相互学习进步 文章目录 1. 题目描述示例1示例2提示 2. 思路3. 代码 1. 题目描述
给你两个单链表的头节点 headA 和 headB 请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点返回 null 。
图示两个链表在节点 c1 开始相交 题目数据 保证 整个链式结构中不存在环。
注意函数返回结果后链表必须 保持其原始结构 。
自定义评测
评测系统 的输入如下你设计的程序 不适用 此输入
intersectVal - 相交的起始节点的值。如果不存在相交节点这一值为 0listA - 第一个链表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 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 中节点数目为 mlistB 中节点数目为 n1 m, n 3 * 1041 Node.val 1050 skipA m0 skipB n如果 listA 和 listB 没有交点intersectVal 为 0如果 listA 和 listB 有交点intersectVal listA[skipA] listB[skipB]
2. 思路 计算两个链表的长度的差值 定义len1表示链表A的长度定义len2表示链表B的长度 int len1 0;
int len2 0;定义指针pl和pspl永远指向最长的链表ps永远指向最短的链表。假设链表A是最长的链表 ListNode pl headA; // 永远指向最长的链表
ListNode ps headB; // 永远指向最短的链表计算链表A和链表B的长度 while (pl ! null) {len1;pl pl.next;
}
while (ps ! null) {len2;ps ps.next;
}pl和ps分别指两个链接的头节点 pl headA;
ps headB;计算链表的差值如果链表A的长度小于链表B的长度则交换pl和ps的指向的头节点重新计算链表的差值。 int len len1 - len2;
if (len 0) {pl headB;ps headA;len len2 - len1;
}让长的链表先移动len步。 while (len ! 0) {pl pl.next;len--;
}同时移动相遇之后就是相交的节点 while (pl ! ps) {pl pl.next;ps ps.next;
}返回pl return pl;运行结果 这样就完了链表一定可以相交如果链表为空呢null ! null为假直接返回pl而pl正好为空 解决方法判断链表是否为空。
while(pl ! null ps ! null pl ! ps) {pl pl.next;ps ps.next;
}
if(pl ps pl null) {return null;
}
return pl;3. 代码
/*** 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) {int len1 0;int len2 0;ListNode pl headA;ListNode ps headB;while (pl ! null) {len1;pl pl.next;}while (ps ! null) {len2;ps ps.next;}pl headA;ps headB;int len len1 - len2;if (len 0) {pl headB;ps headA;len len2 - len1;}while (len ! 0) {pl pl.next;len--;}while(pl ! null ps ! null pl ! ps) {pl pl.next;ps ps.next;}if(pl ps pl null) {return null;}return pl;}
}运行结果
