Write a program to find the node at which the intersection of two singly linked lists begins.

 

For example, the following two linked lists:

A:          a1 → a2                   ↘                     c1 → c2 → c3                   ↗            B:     b1 → b2 → b3

begin to intersect at node c1.

 

Notes:

• • If the two linked lists have no intersection at all, return null.
  • The linked lists must retain their original structure after the function returns.
  • You may assume there are no cycles anywhere in the entire linked structure.
  • Your code should preferably run in O(n) time and use only O(1) memory.

 

也挺简单的，不过我比较粗心，还是很多小细节没有注意。每次变量一多，我就快烦死了== 

刚开始取得两个列表的长度，要对其才可以判断。其他的没有什么注意的点了。

/** * 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 lengthA=0,lengthB=0,d=0;        ListNode* tempA=headA,*tempB=headB;        while(tempA!=NULL){lengthA++;tempA=tempA->next;}        while(tempB!=NULL){lengthB++;tempB=tempB->next;}        tempA=headA;tempB=headB;        if(lengthA>lengthB){            d=lengthA-lengthB;            while(d--) tempA=tempA->next;        }        else{            d=lengthB-lengthA;            while(d--) tempB=tempB->next;        }        d=min(lengthA,lengthB);        while(d--){            if(tempA==tempB) return tempA;            else{ tempA=tempA->next;                  tempB=tempB->next;}        }        return NULL;                    }};