Advertisement
Rohit4Pal

Untitled

May 15th, 2022
820
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. ListNode *detectLoop(ListNode *head){
  2.    
  3.     ListNode *slow=head,*fast=head;
  4.     while(fast != NULL && fast->next != NULL){
  5.         fast=fast->next->next;
  6.         slow=slow->next;
  7.        
  8.         if(slow==fast)
  9.             return slow;
  10.     }
  11.     return NULL;
  12. }
  13.  
  14. ListNode* getIntersectionNode(ListNode *A, ListNode *B) {
  15.    
  16.     //make any one list as circular
  17.     ListNode *p=A;
  18.     while(p->next != NULL)
  19.         p=p->next;
  20.    
  21.     ListNode *last=p;
  22.     p->next=A;
  23.    
  24.     //Now A is circular and this problem is converted into
  25.     //find loop in a LL
  26.     ListNode *q=detectLoop(B);
  27.     //p=detectLoop(B);
  28.    
  29.     if(!q)  {
  30.         last->next=NULL;
  31.         return NULL;
  32.     }  
  33.    
  34.     p=B;
  35.     while(p != q){
  36.         p=p->next;
  37.         q=q->next;
  38.     }
  39.    
  40.     last->next=NULL;
  41.     return p;
  42. }
Advertisement
RAW Paste Data Copied
Advertisement