Leetcode daily practice - 160. Cross linked list

Preface

Wassup guys！ I am a Edison

It's today LeetCode Upper leetcode 160. Intersecting list

Let’s get it！

---

---

1. Topic analysis

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 two linked lists do not have intersecting nodes , return null .
 
Figure two linked lists at the node c1 Start meeting ：

Subject data Guarantee There is no ring in the whole chain structure .
 
Be careful , Function returns the result , Linked list must Keep its original structure .

Example 1：

Example 2：

Example 3：

2. Thought analysis

If this problem is split , It's actually two steps ：

（1） Judge whether two linked lists intersect
 
（2） Then find the first intersection

Judge the intersection

First of all, we should judge the linked list A and Linked list B Whether it intersects , How to judge ？

1. Train of thought

Just use Linked list A Every node of goes and Linked list B Compare and judge in turn , If there is equality , It's intersection , The first equality is intersection ; conversely , Disjoint
 
But this method requires that A Every node in it goes with B Inside N Compare nodes , If A Yes M Nodes , So time complexity is $O(M\ast N)$.
 
Be careful ： The comparison here is not in the node value , The comparison is The address of the next node stored in the current node .

2. Train of thought two

A Linked list find Tail node ,B Linked list Also found Tail node .
 
When Tail node When the address of is the same , Namely The intersection .
 
The time complexity of this method is ：$O(M+N)$.

Find the intersection point

Since we can judge whether the linked list intersects , So how to find the intersection ？

It's also very simple. , Directly speaking, the method ：

（1） Find out A Linked list The length of La, Then find out B Linked list The length of Lb;
 
（2） If A Linked list Than B Linked list Long , that A Linked list Go ahead La - Lb Step ;
 
（2） When A Linked list go Gap step in the future , let A Linked list and B Linked list Let's go together again , first Address Equal is the intersection .

Be careful ：

If B Linked list Than A Linked list Long , So let's B Linked list Go ahead Lb - La Step ;
 
Why use Long subtract A short ？ Because the result is Positive numbers ah , The value obtained by subtracting these two is Gap step .
 
In fact, this question is a little similar to Last in the list k Nodes be similar .

Implementation steps

Since we should judge the intersection from Head node Start walking to Tail node , So let's redefine the two pointers tailA and tailB Point to respectively Linked list A and Linked list B The head node of , Then start walking back ;

tailA Go ahead , When tailA Go to the Tail node when , Just stop （ Dynamic diagram demonstration ）

then tailB To walk again , When tailB Go to the Tail node when , Just stop （ Dynamic diagram demonstration ）

Be careful ： Here is walking to Tail node , That is to say, when Tail node Of next Point to NULL when , Just stop .

Then take it. tailA and tailB Compare , If their Address equal , Explain the intersection , Just find the intersection ; If Address It's not equal , Just go back to NULL;

since Address equal , Then we need to find the intersection , But we have to find out A Linked list and B Linked list The length of ;

Define two integers lenA and lenB, They are used to express the length , The initial value is set to 1.

Calculation lenA The process of

Calculation lenB The process of

Be careful ：

Why the lenA and lenB Of Initial value Set to 1 Well ？
 
Because the length of the linked list is required , That is to say, go to Tail node It's over ;
 
That is to say, calculate from the first node , When go to Tail node when , ends , amount to Tail node No calculation , So forget it 1 individual .

And then we find Gap step , Give Way Long Let's go first Gap step , Then let's go together ;

here lenB Greater than lenA, Find out Gap step by 1;

So we redefine two pointers ,longtList Point to B The head node of ,shortList Point to A The head node of , And then let longList Go ahead Gap step , That is, go first 1 Step （ Dynamic diagram demonstration ）

Now let longList and shortList Went together , Go to the same position and stop （ Dynamic diagram demonstration ）

Be careful ：

The linked list given in the above figure is B Long ,A short , But the actual situation may be A Long ,B short ; It could be A and B As long as ;
 
So we have to judge the length , Suppose the default is set to A Long ,B short ;
 
If lenA Greater than lenB, So the hypothesis holds , Just ask Gap step ;
 
If lenA Less than lenB, Then it means that the hypothesis is not tenable , Just redefine it .

3. Code implementation

Interface code

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    
    struct ListNode* tailA, *tailB;
    tailA = headA;
    tailB = headB;

    int lenA = 1; //  Deposit A The length of the list 
    int lenB = 1; //  Deposit B The length of the list 

    // A Find the tail node of the linked list 
    while (tailA->next) {
    
        tailA = tailA->next;
        ++lenA;
    }

    // B Find the tail node of the linked list 
    while (tailB->next) {
    
        tailB = tailB->next;
        ++lenB;
    }

    //  If not, return NULL
    if (tailA != tailB) {
    
        return NULL;
    }

    //  The intersection , Find the intersection , Long go first " Gap step ",  Then let's go together 
    struct ListNode* shortList = headA; //  hypothesis A short 
    struct ListNode* longList = headB; //  hypothesis B Long 
    //  If A Is longer than B
    if (lenA > lenB) {
    
        //  Then exchange 
        longList = headA;
        shortList = headB;
    }

    //  Ask for travel distance 
    int gap = abs(lenA - lenB); // abs Is the function of finding the absolute value 

    //  Long step first 
    while (gap--) {
    
        longList = longList->next;
    }

    //  Then walk at the same time 
    while (shortList && longList) {
    
        if (shortList == longList) {
    
            return shortList;
        }
        shortList = shortList->next;
        longList = longList->next;
    }

    //  Add this , Otherwise it will show [ Compilation error ]
    return NULL;
}

Submit results