链表：寻找交叉节点

    寻找两个链表中相交部分的起点，不得改变链表结构，时间复杂性要求为O(n)，空间复杂性为O(1），不相交则返回null

    例如：链表A:        a1->a2->c1->c2->c3 

             链表B: b1->b2->b3->c1->c2->c3

             相交的起点为c1

    思路较简单：链表后部分相同，可以先把链表以后端为基准对齐，再一个一个元素的比较，第一个相同的元素则为相交的起点。（这里认为两个链表只有一个相交点，且相交点之后的部分全都相同，如果这种假设不成立，这种方法无效，不过题目应该是支持这种假设的，否则测试案例肯定通不过）

public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if(headA == null || headB == null) return null; int n1 = 0; int n2 = 0; ListNode p1 = headA; ListNode p2 = headB; while(p1 != null){    //计算A链表的长度 n1++; p1 = p1.next; } while(p2 != null){    //计算B链表的长度 n2++; p2 = p2.next; } if(n2>n1){    //把p1指向较长的链表，n1代表较长链表的长度，省去分类判断 p1 = headB; p2 = headA; int t = n1; n1 = n2; n2 = t; } else{ p1 = headA; p2 = headB; } for(int i=0; i<n1-n2; i++){    //把较长的链表向前移，直到两个链表末端对齐 p1 = p1.next; } while(p1 != null){ if(p1.val == p2.val) return p1; p1 = p1.next; p2 = p2.next; } return null; }

    以下是大神的作品：

public ListNode getIntersectionNode(ListNode headA, ListNode headB) { //boundary check if(headA == null || headB == null) return null; ListNode a = headA; ListNode b = headB; //如果a和b的长度不相等，那么下面的循环会循环两次，第一次循环后把两个链表的指针交换，同时完成末端对齐。大神就是大神。。 while( a != b){     //for the end of first iteration, we just reset the pointer to the head of another linkedlist a = a == null? headB : a.next; b = b == null? headA : b.next; } return a; }