leetcode_程序员面试金典0207

思路:滑动窗口+双指针

1.首先遍历两个链表,求出shortList和longList的长度blen和alen。

2.指针p1指向shortList的首元素,指针p2直接找到longList的alen-blen+1个元素,通过p1和p2的比较,如果相等,则找到共同起点,如果不相等,则各自后移一个元素。

3.正确性:因为两个链表最大共同元素个数为blen,且两者共同元素都是位于链表最后,所以长度较长的链表前面那些元素可以不用给予考虑;同样道理,当p1和p2不相等,则说明目标肯定在p1和p2之后。

代码:

/**
 * 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 alen=0;
           int blen=0;
           ListNode *p1=headA;
           for(alen=0;p1;alen++)
                p1=p1->next;
           ListNode *p2=headB;
           for(blen=0;p2;blen++)
                p2=p2->next;
            if(alen<blen)
            {
     
                swap(headA,headB);
                swap(alen,blen);
            }
            p1=headA;
            while(alen>blen)
            {
     
                p1=p1->next;
                alen--;
            }
            p2=headB;
            while(blen--)
            {
     
                if(p1==p2)
                {
     
                    return p1;
                }
                else
                {
     
                    p1=p1->next;
                    p2=p2->next;
                }
            }
            return NULL;
    }
};

你可能感兴趣的