海外建站推广,企业网站建设对企业客户的意义,上海做外贸网站,seo营销软件LeetCode#xff1a;相交链表
一、题目描述
给你两个单链表的头节点 headA 和 headB #xff0c;请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点#xff0c;返回 null 。
二、分析及代码
方法一#xff1a;使用哈希Set集合
#xff08;注意…LeetCode相交链表
一、题目描述
给你两个单链表的头节点 headA 和 headB 请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点返回 null 。
二、分析及代码
方法一使用哈希Set集合
注意集合中存储的是ListNode节点的地址并非数值***换句话说即使链表A和链表B都有值为1的节点但实质上其还是两个不同的节点因为内存地址是不一样的只有都指向同一个相交的节点了其内存地址才是相同的
判断两个链表是否相交可以使用哈希集合存储链表节点。
首先遍历链表 headA并将链表 headA 中的每个节点加入哈希集合中。然后遍历链表 headB对于遍历到的每个节点判断该节点是否在哈希集合中
如果当前节点不在哈希集合中则继续遍历下一个节点如果当前节点在哈希集合中则后面的节点都在哈希集合中即从当前节点开始的所有节点都在两个链表的相交部分因此在链表 headB中遍历到的第一个在哈希集合中的节点就是两个链表相交的节点返回该节点。如果链表 headB 中的所有节点都不在哈希集合中则两个链表不相交返回 null。
上代码
public ListNode getIntersectionNode1(ListNode headA, ListNode headB) {if (headA null || headB null) {return null;}//声明集合SetSetListNode set new HashSet();ListNode temp headA;while (temp ! null) {set.add(temp);temp temp.next;}temp headB;while (temp ! null) {if (set.contains(temp)) {return temp;}temp temp.next;}return null;}方法二两层while循环遍历
注意使用此方法注意while循环的判断条件是对headA 和 headB判断而不是headA.next 和 headB.next因为会有这种情况链表A和链表B都只要一个节点且为同一个节点的情况 上代码
public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {if (headA null || headB null) {return null;}ListNode p headA;while (p ! null) {ListNode q headB;while (q ! null) {if (p q) {return p;}q q.next;}p p.next;}return null;}
