My AC C++ Solution of intersection of Two Linked Lists with O(m+n) time and O(1) space


  • 1
    J
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
            if(headA==NULL || headB==NULL)
    			return NULL;
    
    		ListNode *slow=headA;
    		ListNode *fast=headA;
    		ListNode *pre;
    		ListNode *lastA;//record A's tail
    
    		while(fast != NULL && fast->next != NULL)
    		{
    			slow=slow->next;
    			pre=fast->next;
    			fast=pre->next;
    		}
    		//connect B to A's tail and determine whether there is a loop and find the intersection
    		if(fast != NULL)
    		{
    			lastA=fast;
    			lastA->next=headB;
    		}
    		else
    		{
    			lastA=pre;
    			lastA->next=headB;
    			fast=headB;
    		}
    		while(fast != NULL && fast->next != NULL)
    		{
    			slow=slow->next;
    			fast=fast->next->next;
    
    			if(slow==fast)//if fast can reach slow, there is a intersection
    				break;
    		}
    
    		//no intersection 
    		if(fast==NULL || fast->next==NULL)
    		{
    			lastA->next=NULL;//recover A's tail
    			return NULL;
    		}
    
    		else
    		{
    			fast=headA;//set fast to the headA and move one step every time
    			while(fast!=slow)
    			{
    				fast=fast->next;
    				slow=slow->next;
    			}
    
    			lastA->next=NULL;//recover A's tail
    			return fast;
    		}
    
        }

  • 0
    G
    This post is deleted!

  • 0
    G

    I use the same method as yours and also set lastA->next=NULL. But it still complains that the linked structure is modified. I don't know why


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.