GIF圖講演算法之相遇-有解無憂

前言

今天給大家帶來一個不是那么難的題目，這個題目的解答方法很多，只要能AC的就是好方法，雖然題目不是特別難但是也是劍指offer上的經典題目所以大家要記得打卡呀，然后今天我們的鏈表板塊就算結束啦，周末的時候我會對鏈表的題目做一個總結，俗話說溫故而知新嘛，好啦廢話不多說，我們一起來看一下今天的題目吧

題目描述：

輸入兩個鏈表，找出它們的第一個公共節點，如下圖，回傳黃色結點即可，

在這里插入圖片描述

題目表達是不是也很簡單，這個題目我的方法一共有兩個，一種就是用HashSet進行存盤，一種就是利用雙指標，大家有更好的可以在下面討論呀，

HashSet

這個方法是比較簡單的，主要思路就是，先遍歷一個鏈表將鏈表的所有值都存到哈希表中，然后再遍歷另一個鏈表，如果發現某個結點在哈希表中已經存在那我們直接回傳該節點即可，代碼也很簡單，

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode tempa = headA;
        ListNode tempb = headB;
        //定義hash表
        HashSet<ListNode> arr = new HashSet<ListNode>();
        while(tempa!=null){
            arr.add(tempa);
            tempa=tempa.next;
        }
        while(tempb!=null){
            if(arr.contains(tempb)){
                return tempb;
            }
            tempb=tempb.next;
        }
        return tempb;
        
    }
}

下面這個方法比較巧妙，不是特別容易想到，大家可以自己實作一下，這個方法也是利用我們的雙指標思想，

下面我們直接看動圖吧，特別直觀，一下就可以搞懂，
在這里插入圖片描述

是不是一下就懂了呀，我們利用雙指標，當某一指標遍歷完鏈表之后，然后掉頭去另一個鏈表的頭部，繼續遍歷，因為速度相同所以他們第二次遍歷的時候肯定會相遇，是不是很浪漫啊！

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //定義兩個節點
        ListNode tempa = headA;
        ListNode tempb = headB;
        //回圈
        while(tempa!=tempb){
          //如果不為空就指標下移，為空就跳到另一鏈表的頭部
           tempa = tempa!=null ? tempa.next:headB;
           tempb = tempb!=null ? tempb.next:headA;
        }
        return tempa;        
    }
}

好啦，鏈表的題目就結束啦，希望大家能有所識訓，下周就要更新新的題型啦，繼續堅持，肯定會有識訓的，

在這里插入圖片描述

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/196759.html

標籤：python

上一篇：K近鄰演算法：機器學習萌新必學演算法

下一篇：神人！用一個專案把23種設計模式與六大原則講的通俗易懂。