資料結構2：求連結串列第一個公共節點

問題

輸入兩個連結串列，找出它們的第一個公共節點。

解答

1.路線交叉法。簡潔，但是難懂

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode *posA = headA;
    struct ListNode *posB = headB;
    if (!headA || !headB)
        return NULL;
    while (posA != posB) {
        posA = (posA ? posA->next : headB);//這裡加括號就很好理解
        posB = posB ? posB->next : headA;
    }
    return posA;
}

2.常規方法，先求兩者長度。

int get_length(struct ListNode *head)
{
    int lenght = 0;
    struct ListNode *p = head;

    while (p != NULL) {
        lenght++;
        p = p->next;
    }

    return lenght;
}

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{
    struct ListNode *p = headA;
    struct ListNode *q = headB;

    int lenA = get_length(headA);
    int lenB = get_length(headB);

    int i = 0;
    if (lenA < lenB) {
        while (i < abs(lenA - lenB)) {
            q = q->next;
            i++;
        }
    } else {
        while (i < abs(lenA - lenB)) {
            p = p->next;
            i++;
        }
    }

    while (p != NULL && q != NULL && p != q) {//注意括號裡是p！=q，而不是p->val!=q->val
        p = p->next;
        q = q->next;
    }

    return p;
}