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

语言: CN / TW / HK

(一)前言

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

剑指 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 春招闯关活动」, 点击查看活动详情

分享到: