我竟从一道算法题中看到了浪漫｜刷题打卡

（一）前言

最近在准备面试，也会每天刷几道算法题，碰巧今天刷到了一道浪漫的算法题，正好趁着活动分享给大家。

剑指 Offer 52. 两个链表的第一个公共节点

（二）题目描述

输入两个链表，找出它们的第一个公共节点。

如下面的两个链表：

在节点 c1 开始相交。则说明他们的第一个公共节点是c1

比如：

上面的两个链表第一个公共节点就是8

（三）思路分析

这道题不算难，这里使用两个指针nodeA和nodeB，NodeA指向链表A的表头，NodeB指向链表B的表头。当NodeA走到底时指向链表B的表头重新走，NodeB走到底时指向链表A的表头重新走。直到两个指针相遇。两个指针是一定会相遇的，因为两个指针最后走过的路程都是一样的。

以上图为例：

三段路，指针A走的路是A+C+B，指针B走的路是B+C+A，如果有公共部分，就会在第一个点相遇。如果没有公共部分，则只能在全走完等于null的时候相遇。

（四）AC代码

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;
        }
        return node1;
    }
}
复制代码

（五）总结

《你的名字》的剧情不就是和这个算法一样：你变成了我，走过我走过的路；我变成了你，走过你走过的路；终有一天，我们会相遇。

如果我们注定有同一个未来，只需要彼此不断前进，我是鱼仔，我们下期再见。

本文正在参与「掘金 2021 春招闯关活动」, 点击查看活动详情