Leetcode interview question 02.07 Linked list intersection [double pointer]

LeetCode Interview questions 02.07. The list intersects

1. subject

2. Ideas

It should be noted that ：

1. If two linked lists intersect , From the intersection point to the end of the table are the same nodes , That is, the two become one .
2. The intersection here is determined by reference ！ That is, the address of the node , Not the value of the node ！

Ideas ：

1. Count the length of two linked lists , Subtraction .
another ： I thought about it a little more here , Go to the last node and judge whether they are the same , That is, judge whether the two linked lists intersect .
2. According to the form of tail alignment , The pointer of the long linked list goes first , Go until it is aligned with the header of the short linked list .
3. The two pointers go synchronously , Stop if intersecting .

3. Code implementation

class Solution {
    
public:
 	ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    
 		//1. Special judgment head node ,  There is really no way to intersect an empty table  
 		if(headA == NULL || headB == NULL) return NULL;// If it is empty, there is no ? exactly  
		
		//2. Create a dummy node - It is convenient for the pointer to stop at the last node when counting the length  
 		ListNode* dummyA = new ListNode(-1);
 		dummyA->next = headA;
 		ListNode* dummyB = new ListNode(-1);
 		dummyB->next = headB;
        ListNode*a = dummyA;
        ListNode*b = dummyB;
        int sizeA = 0;int sizeB = 0;
        
        //3. Statistical length   At this time, the pointer points to the last node , Not empty ！
       	while(a->next != NULL) 
       	{
    
       		a = a->next;
       		sizeA++;
		}
        while(b->next != NULL)
        {
    
        	b = b->next;
        	sizeB++;
		}
		delete dummyA;delete dummyB;// Deleting is a good habit  
		
		//4. If the position of the last node is the same , Is intersecting .  Discussion by situation  
		if(a == b) 
		{
    
			if(sizeA > sizeB)//A Than B Long  
			{
    
				//5. Length difference  
				int cnt = sizeA - sizeB;
				ListNode* fast = headA;
				ListNode* slow = headB;
				
				//6. Let's go first , Align with the head of the slow pointer  
				while(cnt--) 
					fast = fast->next; 
				
				//7. Go at the same time , When you encounter the starting point of intersection, you return  
				while(fast != slow)
				{
    
					fast = fast->next;
					slow = slow->next;
				 } 
				 ListNode *m = fast;
				 return m;
			}
			else //if(sizeA <= sizeB) B Than A Long or equal  
			// It can only be else, The compiler thinks there are other cases ...
			{
    
				int cnt = sizeB - sizeA;
				ListNode* fast = headB;
				ListNode* slow = headA; 
				while(cnt--) 
					fast = fast->next; // Align with the head of the slow pointer 
				while(fast != slow)
				{
    
					fast = fast->next;
					slow = slow->next;
				 } 
				 ListNode *m = fast;
				 return m;
			}
		}
		else return NULL;// Disjoint , Go straight back to  
    }
};

Post a more concise code of the boss , Redundant code generated by case discussion is omitted , Because it can be exchanged directly ！ Just a little bit .

 		curA = headA;
        curB = headB;
        //  Give Way curA For the head of the longest linked list ,lenA Is its length 
        if (lenB > lenA) {
    
            swap (lenA, lenB);//lenA Save large value 
            swap (curA, curB);//curA Refers to the head of the long linked list 
        }
        //  Length difference 
        int gap = lenA - lenB;
        //  Length difference 
        int gap = lenA - lenB;
        //  Give Way curA and curB At the same starting point （ End position alignment ）
        while (gap--) {
    
            curA = curA->next;
        }
        //  Traverse curA  and  curB, If you encounter the same, you will directly return 
        while (curA != NULL) {
    
            if (curA == curB) {
    
                return curA;
            }
            curA = curA->next;
            curB = curB->next;
        }
        return NULL;

matters needing attention

There is a small one. tip: Count the length of the linked list. If you want the pointer to stop at the last node, you can use dummy nodes ！
swap function ： Exchange values at respective addresses . such as swap(a,b);a,b Are variables of the same data type .a,b The values of are assigned to b,a.