兰州新区规划建设管理局网站制作灯笼的材料

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;}//声明集合SetSet<ListNode> 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;}