惠州专业网站设计公司,下载的网站模板怎么修改,上海网站建设 zl,上海网站建设服务商题目#xff1a;160. 相交链表 给你两个单链表的头节点 headA 和 headB #xff0c;请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点#xff0c;返回 null 。 图示两个链表在节点 c1 开始相交#xff1a; 题目数据 保证 整个链式结构中不存在环。 注意…题目160. 相交链表 给你两个单链表的头节点 headA 和 headB 请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点返回 null 。 图示两个链表在节点 c1 开始相交 题目数据 保证 整个链式结构中不存在环。 注意函数返回结果后链表必须 保持其原始结构 。 自定义评测 评测系统 的输入如下你设计的程序 不适用 此输入 intersectVal - 相交的起始节点的值。如果不存在相交节点这一值为 0listA - 第一个链表listB - 第二个链表skipA - 在 listA 中从头节点开始跳到交叉节点的节点数skipB - 在 listB 中从头节点开始跳到交叉节点的节点数 评测系统将根据这些输入创建链式数据结构并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点那么你的解决方案将被 视作正确答案 。 解题思路
根据题目要求得知要求求出两条链表的相交节点首先判断是否有一个或者两个都是空值如果是则肯定没有相交点直接返回null如果两个链表都有值则开始判断是否有相交点
依然是两种方法
第一种哈希集合-HashSet
用 HashSet 存入第一个链表的所有节点再遍历第二个链表判断哈希集合中是否含有第二个链表的节点有的话直接返回节点没有则返回 null 。
第二种指针思路
假设两个指针分别从两个链表头部开始遍历如果指针指代的节点一致则说明相等就跳出遍历如果不一致则继续遍历直到相等如果两个链表不相交则两个指针最后值为 pA pB null。
解题过程
第一种
/*** 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) {SetListNode setNode new HashSetListNode();ListNode temp headA;while (temp ! null) {setNode.add(temp);temp temp.next;}temp headB;while (temp ! null) {if(setNode.contains(temp)) {return temp;}temp temp.next;}return null;}
}
第二种
/*** 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) {if(headA null || headB null) {return null;}ListNode pA headA, pB headB;while(pA ! pB) {pA pA null ? headB : pA.next;pB pB null ? headA : pB.next;}return pA;}
}
