160. 相交链表

【题目】：160. 相交链表

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* a = headA, *b = headB;
        while(a != b) {
            a = (a != NULL ? a->next : headB);
            b = (b != NULL ? b->next : headA);
        }
        return a;
    }
};

• 时间复杂度: O(a + b)
• 空间复杂度: O(1)

这题可以将headA遍历完后遍历headB，把headB遍历完后遍历headA，这样就相当于走了同样的距离。

不管什么情况，都会退出循环，且都只会遍历（a+b）次，不会有死循环的情况。