Leetcode: 160. 相交链表
两种解法:双指针法和哈希表法。
1. 双指针法
思路:链表 A 和 B 同时登程,链表 A 走到开端,跳到 B 的结尾持续走,B 走到开端,同样跳到 A 持续走,如果 A,B 不相等,继续执行,如果 A,B 相等,有两种可能:①A=B=null,A 和 B 都来到了各自的开端,A,B 无交点。②A=B= 链表交点,该状况 A,B 存在交点,这时返回 A,B 任一节点即可。因而如果两个链表相交,返回的值是两链表第一个交点,如果不相交,返回的是 null。
// 双指针法
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {if(headA == null || headA == null) return null;
ListNode A = headA,B = headB;
while(A!= B){
A = A == null?headA:A.next;
B = B == null?headB:B.next;
}
return A;
}
}
2. 哈希表法
(1)如果指向链表的指针 A 或者 B 任何一个为空,则没有交点,返回 null
(2)把链表 A 所有节点退出先 hashset
(3)遍历链表 B,在遍历过程中的节点如果在 hashset 中存在,则阐明该节点为公共节点,如果最终遍历完没有节点存在 hashset 中,两链表不相交,则返回空。
// 哈希表法
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {if(headA == null || headB == null) return null;
HashSet<ListNode> set = new HashSet<ListNode>();
while(headA != null){set.add(headA);
headA = headA.next;
}
while(headB != null){if(set.contains(headB)){return headB;}
headB = headB.next;
}
return null;
}
}