题目：相交链表.- 力扣（LeetCode）
第一思路：
先扫一遍两个链表，找到他两的长度m,n,将他俩移到相同的位置上，此时两个链表等长。然后开始等长的判断，如果走到相交的点。
时间复杂度 O(m + n), 空间复杂度O(1)
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {if (headA == NULL || headB == NULL) return NULL;ListNode *p = headA, *q = headB;int m = 0, n = 0;while(p != NULL){p = p->next;m ++;}while(q != NULL){q = q->next;n ++;}p = headA, q = headB;if(m > n){while(m != n){p = p->next;m --;}}else {while(m != n){q = q->next;n --;}}while(p != q){p = p->next;q = q->next;}return p;}
};
第二思路：
如果B走完后就走A走过的路，如果走不到就更换另外一个链表走，这样，实际上是一个寻找子串的过程。这样，时间复杂度可以进一步优化到O(n)
举例：
1->2->3->4->5->6->3
3->4->5->6->1->2->3
思考：代码重与重新走headA而不是走headB的区别是什么？
如果重新走A，虽然仍能通过此题，但是实际上走了k * n + b == t * m + b的距离，成为了循环判断两个是否相同。而更换头以后，是在一个M + N中进行判断，最后在max（m，n）进行了判断，思路一则是m + n + b。
其中b为到相同节点的偏移量。
m，n为两个链表的长度。
k，t为两个链表的倍增值。
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {if (headA == NULL || headB == NULL) return NULL;ListNode *p = headA, *q = headB;while (p != q) {p = p == NULL ? headB : p->next;q = q == NULL ? headA : q->next;}return p;}
};
)
