【LeetCode刷题】相交链表问题:妙解

  • /**  这个可太难想到了,双指针法!
  •  * Definition for singly-linked list. 
  •  * struct ListNode { 
  •  *     int val; 
  •  *     ListNode *next; 
  •  *     ListNode(int x) : val(x), next(NULL) {} 
  •  * }; 
  •  */  
  •  auto speedup=[](){  
  •     std::ios::sync_with_stdio(false);  
  •     cin.tie(nullptr);  
  •     cout.tie(nullptr);  
  •     return nullptr;  
  • }();  
  • class Solution {  
  • public:  
  •     ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {  
  •         /** 
  •         a  
  •             -  c  
  •         b / 
  •         a->end : a+c    a移到b head 
  •         b->end : b+c    b移到a head 
  •         会在a+b+c 步之后再交汇点相遇 
  •         如果有交点 会在交点相会 
  •         如果没有交点会同时到达NULL 
  •         */  
  •         if(headA == NULL || headB == NULL){  
  •             return NULL;  
  •         }  
  •         ListNode * la = headA;  
  •         ListNode * lb = headB;  
  •         while(la != lb){  
  •             la = la ? la->next : headB;  
  •             lb = lb ? lb->next : headA;  
  •         }  
  •         return la;  
  •     }  
  • };  

       

    来自 <http://www.planetb.ca/projects/syntaxHighlighter/popup.php>

原文地址:https://www.cnblogs.com/xukaiae86/p/11857943.html