[LeetCode] 160. Intersection of Two Linked Lists

陪她去流浪 桃子 2017年02月04日 编辑 阅读次数:2162

链接: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;
}

标签:LeetCode