相交链表

思路：我们计算A和B链表的长度，求出他们的差值（len），让链表长的先多走len步，最后在A,B链表一起向后走，即可相逢于相交节点

实现代码如下：

public class Solution {public int size(ListNode phead){if(phead==null){return 0;}ListNode cur=phead;int count=0;while(cur!=null){count++;cur=cur.next;}return count;}public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode pl=headA;//longListNode ps=headB;//shortint lenA=size(pl);int lenB=size(ps);if(headA==null||headB==null){//如果其中一个链表为空，则不存在相交节点，直接返回nullreturn null;}if(lenA>lenB){//如果A链表长度 > B链表，让pl引用指向A链表//ps引用指向B链表pl=headA;ps=headB;}else {//如果A链表长度 < B链表，让ps引用指向A链表//pl引用指向B链表ps=headA;pl=headB;}//计算两链表的长度差int len=0;if(lenA>lenB){len=lenA-lenB;}else {len=lenB-lenA;}//让长链表先多走len步while (len!=0){pl=pl.next;len--;}while(pl!=null){//若节点的next域指向相同，则说明找到了相交节点if(pl==ps){return ps;}pl=pl.next;ps=ps.next;}//链表走到底，为空了，还没有找到，就说明不存在相交节点，返回nullreturn null;}
}