算法基础~链表~求两个链表的交点( 时间复杂度O(n)、空间复杂度O(1）)
1，接着上一篇的优化思路：https://www.cnblogs.com/shan333/p/15033376.html
2，还记得上篇中说到：
“【为什么要以其中一条链为参照链？ because：链表的长度不一，
例如图解(图在上一篇随笔中) A链表的长度明显就是长于B链表的，如果不以其中某一条链表为参照链，则A、B链表不可能相遇！】”~于是乎，咱的思路就呼吁而出啦！
3，设想一下链表A、B长度相同时，A、B同步移动，每移动一个结点便做一次比较地址，当比较的地址相同则找到了交点啦
~【这个过程并不需要额外申请其他空间~空间复杂度O(1)；】 【A、B链表是同步移动，可以在同一循环里一起遍历~时间复杂度O(n)】
4，直接上代码，解释在2、3有：
public class Solution { //获取链表的长度 int get_list_length(ListNode *head){ int len = 0; while(head){ len++; head = head->next; } return len; } //对齐链表，将链表长度较长的链表移动到与另外一条链表对齐后返回 ListNode *forward_long_list(int long_len, int short_len, ListNode *head){ int delta = long_len - short_len; while(head && delta){ head = head->next; delta--; } return head; } public : ListNode *getIntersectionNode(ListNode *headA, ListNode *headB){} int list_A_len = get_list_length(headA); int list_B_len = get_list_length(headB); //A链表比较长时 if(list_A_len > list_B_len){ headA = forward_long_list(list_A_len, list_B_len, headA); }else{ headB = forward_long_list(list_B_len, list_A_len, headB); } //同时遍历A、B链表，比较地址 while(headA && headB){ if(headA == headB){ return headA; } headA = headA->next; headB = headB->next; } return NULL; }
