(1) Preface

Recently, I am preparing for the interview, and I will brush several algorithm questions every day. Today, I happened to brush a romantic algorithm question, just taking advantage of the activity to share with you.

Sword refers to Offer 52. The first common node of two linked lists

(2) Title description

Enter two linked lists to find their first common node.

Here are two linked lists:

The intersection begins at node C1. That means their first common node is C1

Such as:

The first common node in the two lists above is 8

(3) Train of thought analysis

NodeA refers to the head of linked list A, and nodeB refers to the head of linked list B. When NodeA reaches bottom, it redirects to the head of linked list B, and when NodeB reaches bottom, it redirects to the head of linked list A. Until the two Pointers meet. The two Pointers are bound to meet, because they both end up traveling the same distance.

The above picture shows an example:

Three paths, pointer A goes A+C+B, pointer B goes B+C+A, if there is A common part, it will meet at the first point. If there are no common parts, they can only be met when all walks are equal to null.

(iv) AC code

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode node1=headA,node2=headB;
        while(node1! =node2){ node1=node1! =null? node1.next:headB; node2=node2! =null? node2.next:headA; }returnnode1; }}Copy the code

(5) Summary

“Your Name” is all about this algorithm: you become me, you walk the path I walk; I became you, walked the road you walked; One day, we will meet.

If we’re meant to have the same future, we just need to keep moving forward. I’m Fish boy. See you next time.

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign