考虑有交集的两条链表A, B, 如题中的
A: a1 -> a2 ->
c1 -> c2 -> c3.
B: b1 -> b2 -> b3 ->
发现有性质:AB不同串(a1a2和b1b2b3)的长度差 即为AB串的长度差。
所以我们先求出AB串的长度差,再将较长的串移进相应的长度差,得到两条长度相等串,再同时移动headA\B即可。
代码:
class Solution {public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB){int a_len=0, b_len=0;for (auto tmp=headA; tmp!=NULL; tmp=tmp->next, ++ a_len) {}for (auto tmp=headB; tmp!=NULL; tmp=tmp->next, ++ b_len) {}if (a_len > b_len){for ( ; a_len>b_len; headA=headA->next, — a_len) {}} else if (b_len > a_len){for ( ; b_len>a_len; headB=headB->next, — b_len) {}}while (headA != NULL){if (headA == headB){return headA;} else{headA = headA->next;headB = headB->next;}}return NULL;}};
,自己打败自己的远远多于比别人打败的。