2 相交链表

1 常规思路

比较两个链表的长度，然后让较短的链表走二者长度之差，此时两个链表就一样长了，开始用双指针遍历，如果有相等返回，没有返回null；

为了减少冗余代码，我们设置一个minCur和maxCur分别代表短长链表，让长链表走即可

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {int l = 0;int s = 0;ListNode cur = headA;while(cur != null) {l++;cur = cur.next;}cur = headB;while (cur != null) {s++;cur = cur.next;}ListNode lNode = headA;ListNode sNode = headB;if(l - s < 0) {int tem = s;s = l;l = tem;lNode = headB;sNode = headA;}int result =l - s;while(result > 0) {lNode = lNode.next;result--;}while(lNode != null && sNode != null ) {if(lNode == sNode){return lNode;}lNode = lNode.next;sNode = sNode.next;}return null;}
}

方法二：

一直循环遍历两个链表，如果二者有重复节点那么肯定会相遇，没有也会在某一时刻返回空（看看即可）

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {if (headA == null || headB == null) {return null;}ListNode pA = headA, pB = headB;while (pA != pB) {pA = pA == null ? headB : pA.next;pB = pB == null ? headA : pB.next;}return pA;}
}

其中应该交替循环，不然时间复杂度会很大(没搞清原理)

方法三：

遍历一个链表，放到hash中，在遍历另一个链表，看哈希表中是否存在

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {Set<ListNode> visited = new HashSet<ListNode>();ListNode temp = headA;while (temp != null) {visited.add(temp);temp = temp.next;}temp = headB;while (temp != null) {if (visited.contains(temp)) {return temp;}temp = temp.next;}return null;}
}