[LeetCode] 160. Intersection of Two Linked Lists

链接：160. Intersection of Two Linked Lists

描述：寻找两个单链表的开始交叉结点。

举例：

A:        a1 -> a2
                   \
                    c1 -> c2 -> c3
                   /
B:  b1 -> b2 -> b3

那么，交叉开始结点应该是 c1。

要求：

• 如果没有交叉，应返回 NULL；
• 不要对链表作任何修改；
• 不用考虑链表有环的情况；
• O(n) 时间复杂度，O(1) 空间复杂度；

思路：如果两个链表有交叉，并且如果交叉结点前面的结点个数相等的话，那么，可以采用同时前进结点指针的办法，当两个指针第一次相等时，就找到了。于是，问题转化成了怎么使两个链表长度相等，很简单了，较长的链表向前移动若干个结点，让其与较短的结点长度相等即可。

代码：

#include "stdafx.h"

using namespace std;

struct ListNode
{
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution
{
public:
    ListNode* getIntersectionNode(ListNode* headA, ListNode* headB)
    {
        int na = size(headA);
        int nb = size(headB);

        if(na > nb) {
            for(int diff = na - nb; diff; --diff)
                headA = headA->next;
        }
        else if(na < nb) {
            for(int diff = nb - na; diff; --diff)
                headB = headB->next;
        }

        while(headA != headB) {
            headA = headA->next;
            headB = headB->next;
        }

        return headA;
    }

    int size(ListNode* head)
    {
        int n = 0;
        while(head) {
            n += 1;
            head = head->next;
        }
        return n;
    }
};

int main_160()
{
    ListNode a1(1), a2(2), c1(1), c2(2), c3(3), b1(1), b2(2), b3(3);

    a1.next = &a2;
    a2.next = &c1;

    b1.next = &b2;
    b2.next = &b3;
    b3.next = &c1;

    c1.next = &c2;
    c2.next = &c3;
    c3.next = NULL;

    cout << &c1 << endl;

    Solution so;
    cout << so.getIntersectionNode(&a1, &b1) << endl;

    return 0;
}