160. 相交链表

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution 
10 {
11 public:
12     ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) 
13     {
14         if(headA == NULL || headB == NULL) return NULL;
15         int lenA = 0,lenB = 0;
16 
17         ListNode* tempA = headA;//求链表长度不要直接用headA，用一个临时对象
18         ListNode* tempB = headB;
19         while(tempA || tempB)
20         {
21             if(tempA) lenA++,tempA = tempA->next;
22             if(tempB) lenB++,tempB = tempB->next;
23         }
24 
25         int len = lenA > lenB ? lenA - lenB : lenB - lenA;
26         int step = lenA > lenB ? lenB : lenA;
27         ListNode *first = headA;
28         ListNode *second = headB;
29 
30         if(lenA < lenB) first = headB,second = headA;
31 
32         while(len-- && first) first = first->next;//先走len步后，链表A与B的个数相同
33         
34         while(step-- && first && second)//然后同时走，直到相遇
35         {
36             if(first == second) break;
37             first = first->next,second = second->next;
38         }
39         return first;
40     }
41 };