相交链表

观察了一下，题目的做法和我的做法差不多类似，都是想要从同一身高位置往下找，我是先计算长度，长的人先走来做到同一高度出发

/**
 * 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) {
        int na=0, nb=0;
        for(ListNode* p = headA; p != NULL; p=p->next, ++na);
        for(ListNode* p = headB; p != NULL; p=p->next, ++nb);
 
        ListNode *p=headA, *q=headB;
        if(na > nb) {
            for(int i = 0; i < na-nb; ++i) {
                p = p->next;
            }
        } else {
            for(int i = 0; i < nb-na; ++i) {
                q = q->next;
            }
        }
 
        while(p != NULL) {
            if(p == q) return p;
            else { p=p->next; q=q->next; }
        }
        return NULL;
    }
};

官方题解是同时遍历，到终点就跳到对面，也能做到同一起跑线

时间复杂度一样，但是还是略略快一点

/**
 * 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) {
        ListNode *p=headA, *q=headB;
        while(p != q) {
            p = p == NULL ? headB : p->next;
            q = q == NULL ? headA : q->next;
        }
        return q;
    }
};