160. 相交链表
160. 相交链表
分析
有一点需要注意，链表相交，实际上意味着，两个链表中的节点的 next 指针，指向了同一个对象，这才叫链表相交。
一上来，我就想到了反转链表，先把两个数组都反转了，然后从头开始比较，不就可以了，但是不行，这一题不能这么弄，因为这两个链表的尾部共用了对象，所以当我们把一个链表反转了，另一个链表的元素就被打乱了。无法比较了，所以这个题无法用反转链表。
因为不能用反转链表，所以只能从两个链表的头开始往后遍历，然后对比这两个节点是否相等，这种方式。
笨一点的办法就是，嵌套 for 循环，一个一个比对，这种复杂度是
那有没有高级一点的办法呢?
有，我们先把两个链表的长度算出开，然后长的那个先移动，移动到长度的差值，短的那个再开始准备移动。此时，两个指针到各自链表末尾的距离就是相等的，接下来，我们直接对比这两个指针指向的对象是否相等，不相等就同时移动即可。
解决单向链表倒数第几个元素这类问题的时候，有两种方式，
- 递归
- 间隔固定长度的双指针，类似的用法我们在 19. 删除链表的倒数第 N 个结点 中也已经使用过了
非常好用。
解题
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
int lengthA = getLength(headA);
int lengthB = getLength(headB);
ListNode longHead = headA;
ListNode shortHead = headB;
int length = 0;
if(lengthA>lengthB){
longHead = headA;
shortHead = headB;
length = lengthA-lengthB;
}else if(lengthA<lengthB){
longHead = headB;
shortHead = headA;
length = lengthB-lengthA;
}
if(length>0){
for(int i=0;i<length;i++){
longHead = longHead.next;
}
}
// 此时 longHead 到 shortHead 的距离是 n
while(longHead!=null&&shortHead!=null&&longHead!=shortHead){
longHead = longHead.next;
shortHead = shortHead.next;
}
// 如果两个链表确实不相交，那么shortHead和longHead最后就会双双迭代为 null
return longHead;
}
public int getLength(ListNode head){
int length = 1;
while(head.next!=null){
head = head.next;
length++;
}
return length;
}