11_160. 相交链表
题目描述：
解题思路：
- 想到了之前考研时候做过的一道题，如果链表相交，那么自相交节点开始，后面的序列是相同的。因此可以通过遍历两个链表，得到链表长度，获得链表长度差k。然后让长链表先遍历k步，再同时遍历两个链表，如果遍历到相交节点，则两个节点是同一个，如果不是相交链表，等遍历结束时，该节点是null。
- 哈希表：将链表A添加到Hash表中，然后依次遍历链表B，如果链表B的节点存在于链表A的节点，那么表示相交。
- 双指针：两个指针都从头开始同时遍历，假设两个链表分别为m，n，A链表相交前的部分是a，B链表是b，相交后的部分是c；如果两个链表长度相同，如果有相交，则直接返回相同的节点即可，如果不相交，则遍历到空值；如果两个链表长度不同，那么当链表A遍历到结束后，从链表B开始遍历，链表B结束后，从A遍历，如果相交，那么当A再到交点的时候是a+c+b，而B恰好也是b+c+a；如果不相交，那么两者节点不相同。
注意：并不会出现相交后在分离的情形，因为相交必然是同一个节点，如果分离，需要有两个next
代码：
先消除长度差，同时双指针遍历
//先消除长度差，同时双指针遍历
/**
* 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;
}
int aLen = 0;
int bLen = 0;
ListNode listA = headA;
ListNode listB = headB;
while (listA != null || listB != null){
if (listA == null){
bLen++;
listB = listB.next;
}else if (listB == null){
aLen++;
listA = listA.next;
}else{
aLen++;
bLen++;
listA = listA.next;
listB = listB.next;
}
}
int k = Math.abs(aLen - bLen);
listA = headA;
listB = headB;
for (int i = 0;i < k;i++){
if (aLen >= bLen){
listA = listA.next;
}else{
listB = listB.next;
}
}
while(listA != null){
if (listA == listB ){
return listA;
}
listA = listA.next;
listB = listB.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) {
//哈希表
HashSet visited = new HashSet<>();
ListNode pA = headA;
while (pA != null){
visited.add(pA);
pA = pA.next;
}
pA = headB;
while (pA != null){
if (visited.contains(pA)){
return pA;
}
pA = pA.next;
}
return null;
}
}
双指针 a+c+b = b+c+a
//双指针 a+c+b = b+c+a
/**
* 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;
ListNode pB = headB;
while (pA != pB){
pA = pA == null ? headB : pA.next;
pB = pB == null ? headA : pB.next;
}
return pA;
}
}