Leetcode interview question 02.07. Linked list intersection [knowledge points: Double pointers, stack]

subject

source ： Power button （LeetCode）
link ： Interview questions 02.07. The list intersects
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .
Here are two head nodes of the single linked list headA and headB , Please find out and return the starting node where two single linked lists intersect . If there is no intersection between two linked lists , return null .

Figure two linked lists at the node c1 Start meeting ：

Subject data Guarantee In the whole chain structure There is no ring .

Be careful , Function returns the result , Linked list must Keep its original structure .

Example 1：

Input ：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
Output ：Intersected at ‘8’
explain ： The value of the intersection node is 8 （ Be careful , If two linked lists intersect, they cannot be 0）.
Starting from the respective heads , Linked list A by [4,1,8,4,5], Linked list B by [5,0,1,8,4,5].
stay A in , There is... Before the intersection node 2 Nodes ; stay B in , There is... Before the intersection node 3 Nodes .

Example 2：

Input ：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output ：Intersected at ‘2’
explain ： The value of the intersection node is 2 （ Be careful , If two linked lists intersect, they cannot be 0）.
Starting from the respective heads , Linked list A by [0,9,1,2,4], Linked list B by [3,2,4].
stay A in , There is... Before the intersection node 3 Nodes ; stay B in , There is... Before the intersection node 1 Nodes .

Example 3：

Input ：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output ：null
explain ： Starting from the respective heads , Linked list A by [2,6,4], Linked list B by [1,5].
Because these two linked lists don't intersect , therefore intersectVal It has to be for 0, and skipA and skipB It could be any value .
The two lists don't intersect , Therefore return null .

Tips ：

• listA The number of nodes in is m
• listB The number of nodes in is n
• 0 <= m, n <= 3 * 104
• 1 <= Node.val <= 105
• 0 <= skipA <= m
• 0 <= skipB <= n
• If listA and listB There is no point of intersection ,intersectVal by 0
• If listA and listB There are intersections ,intersectVal == listA[skipA + 1] == listB[skipB + 1]

** Advanced ：** Can you design a time complexity O(n) 、 Just use O(1) Memory solutions ？

Problem solving

Method 1 ： Violence enumeration

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */
  
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
    
    struct ListNode *p,*q;

    for(p=headA;p;p=p->next){
    
        for(q=headB;q;q=q->next){
    

            if(p == q){
    
                goto HERE;
            }
        }
    }

    HERE: return p;
}

Time complexity O(m*n), Spatial complexity O(1)

Method 2 ： Stack

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */

#define MAXNUMS 30001

typedef struct _Stack{
    
    struct ListNode* Array[MAXNUMS];
    int Top;
}Stack;

void Push( Stack* S,struct ListNode* p )
{
    
    S->Top++;

    if(S->Top < MAXNUMS){
    
        S->Array[S->Top] = p;
    } 
}

struct ListNode* Pop( Stack* S )
{
    
    return S->Array[S->Top--];
}

bool isEmpty ( Stack* S )
{
    
    return S->Top == -1 ? true : false;
}

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
    
    if(headA == NULL || headB == NULL){
    
        return NULL;
    }

    Stack* A = malloc(sizeof(Stack));
    A->Top = -1;

    Stack* B = malloc(sizeof(Stack));
    B->Top = -1;

    struct ListNode *p,*q;

    p = headA;
    while(p){
    
        Push( A,p );
        p = p->next;
    }

    q = headB;
    while(q){
    
        Push( B,q );
        q = q->next;
    }

    struct ListNode *ans;
    p = q = NULL;

    while( p == q && !isEmpty( A ) && !isEmpty( B ) ){
    
        ans = p;
        p = Pop( A );
        q = Pop( B );
    }

    if((isEmpty( A ) || isEmpty( B )) && p == q){
    
        ans = p;
    }

    return ans;
}

Method 3 ： Front and rear double pointers （ Optimal solution of this problem ）

Figure out first. 2 The length of the list , The pointer of the long linked list goes a few more steps first , Make sure the remaining length is equal to the other , then 2 The pointers move back at the same time , Judge whether it points to the same node ;

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */
  
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
    
    struct ListNode *p,*q;
    int La,Lb;
    La = Lb = 0;

    for(p=headA;p;p=p->next,La++);
    for(q=headB;q;q=q->next,Lb++);

    p = headA;
    q = headB;
    int K;

    if(La >= Lb){
    
        K = La -Lb;
        while(K--){
    
            p = p->next;
        }
    }else{
    
        K = Lb - La;
        while(K--){
    
            q = q->next;
        }
    }

    while(p){
    
        if(p == q){
    
            break;
        }else{
    
            p = p->next;
            q = q->next;
        }
    }

    return p;
}

The great god NB Double pointer ：

Consider building two node pointers A​ , B Point to the two chain header nodes respectively headA , headB , Do the following ：

• The pointer A First traverse the linked list headA , Then start traversing the linked list headB , When go to node when , The total number of steps is ：
  a + (b - c)
• The pointer B First traverse the linked list headB , Then start traversing the linked list headA , When go to node when , The total number of steps is ：
  b + (a - c)

It is shown in the following formula , Now the pointer A , B coincidence , And there are two situations ：

a + (b - c) = b + (a - c)

• If two linked lists Yes The public tail ( namely c > 0c>0 ) ： The pointer A , B At the same time point to 「 The first common node 」node .
• If two linked lists nothing The public tail ( namely c = 0c=0 ) ： The pointer A , B At the same time point to nullnull .
  Therefore return A that will do .

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
    
    struct ListNode *A,*B;
    A = headA;
    B = headB;

    while(A != B){
    
        A = A==NULL ? headB : A->next;
        B = B==NULL ? headA : B->next;
    }
    
    return A;
}

This code is so beautiful _{！！！ A great god NB}！！