给定两个（单向）链表，判定它们是否相交并返回交点。请注意相交的定义基于节点的引用，而不是基于节点的值。换句话说，如果一个链表的第k个节点与另一个链表的第j个节点是同一节点（引用完全相同），则这两个链表相交。
示例 1：
输入：listA = [4,1,8,4,5], listB = [5,0,1,8,4,5]
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
正解
1)第一种思路：历遍链表1或2，每次令其历遍元素指向另一个链表的头，并以该元素为起点进行历遍，若size等于另一个链表的长度，那么该元素不为相交点；若陷入循环(size>另一个链表的长度)则证明是交叉点。历遍元素的指针每次要做到复原。[时间复杂度O(n+n*2)]
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode dummyHeadA = new ListNode(0);
ListNode dummyHeadB = new ListNode(0);
dummyHeadA.next = headA;
dummyHeadB.next = headB;
ListNode copy=null;
ListNode ret = null;
ListNode temp = null;
int size = 0;
if (headA != null && headB != null) {
while (dummyHeadB.next != null) {//获取另一链表的长度
dummyHeadB = dummyHeadB.next;
size++;
}
while (dummyHeadA.next != null) {
dummyHeadA = dummyHeadA.next;
copy=dummyHeadA;//记录当前节点
if (dummyHeadA.next != null) {//记录下一个节点
temp = dummyHeadA.next;
}else {
temp=null;
}
dummyHeadA.next = headB;//将HeadA指针移至HeadB
if (isSame(dummyHeadA, size)) {//如果当前节点符合条件，复原HeadA指针
if(temp==null){
dummyHeadA.next=null;
}else {
dummyHeadA.next=temp;
}
ret = dummyHeadA;
break;
} else {//如果不符合条件,复原指针
if (temp!=null){
dummyHeadA.next = temp;
}else {//若没有下一节点，复原后返回
dummyHeadA.next=null;
return ret;
}
}
}
}
return ret;
}
public static boolean isSame(ListNode a, int size) {
boolean flag = false;
int count = 0;
ListNode temp = a;
while (temp.next != null) {
temp = temp.next;
count++;
if (count > size) {
flag = true;
break;
}
}
return flag;
}
}2)第二种思路：不难发现第一种思路的解法很耗时间，通过比较，若两者有交叉点，那么共同部分的长度最多为size=Math.min(sizeA,sizeB);设置两个指针分别指向下标为倒数第size的地方，然后依次比较即可。【时间复杂度:O(3n)】
/**
* 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) {
ListNode curA = headA;
ListNode curB = headB;
int lenA = 0, lenB = 0;
while (curA != null) { // 求链表A的长度
lenA++;
curA = curA.next;
}
while (curB != null) { // 求链表B的长度
lenB++;
curB = curB.next;
}
curA = headA;
curB = headB;
// 让curA为最长链表的头，lenA为其长度
if (lenB > lenA) {
//1. swap (lenA, lenB);
int tmpLen = lenA;
lenA = lenB;
lenB = tmpLen;
//2. swap (curA, curB);
ListNode tmpNode = curA;
curA = curB;
curB = tmpNode;
}
// 求长度差
int gap = lenA - lenB;
// 让curA和curB在同一起点上（末尾位置对齐）
while (gap-- > 0) {
curA = curA.next;
}
// 遍历curA 和 curB，遇到相同则直接返回
while (curA != null) {
if (curA == curB) {
return curA;
}
curA = curA.next;
curB = curB.next;
}
return null;
}
}