LeetCode160 交叉链表

编写一个程序，找到两个单链表相交的起始节点。

先遍历一遍两个链表，记录长度，然后将长的那一侧先移动，移动到两个链表剩下的长度相同，然后同步移动两个指针，直到相遇或结束。

注意diff正负的问题，不要diff--导致longer往后移动到null。

 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 public:
11     ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
12         int len1=0,len2=0;
13         ListNode* dummyA=new ListNode(-1),*dummyB=new ListNode(-1);
14         dummyA->next=headA;
15         dummyB->next=headB;
16         while(headA!=nullptr){
17             headA=headA->next;
18             ++len1;
19         }
20         while(headB!=nullptr){
21             headB=headB->next;
22             ++len2;
23         }
24         int diff=len1-len2;
25         ListNode* longer=diff>0?dummyA->next:dummyB->next;
26         ListNode* shorter=diff>0?dummyB->next:dummyA->next;
27         diff=abs(diff);
28         while(diff--)
29             longer=longer->next;
30         ListNode* same=nullptr;
31         while(shorter!=nullptr && longer!=nullptr){
32             if(shorter==longer){
33                 return shorter;
34             }
35             longer=longer->next;
36             shorter=shorter->next;
37         }
38         return nullptr;
39         
40     }
41 };