国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

LeetCode 160： 相交鏈表 Intersection of Two Linked List

wing324 / 1821人閱讀

摘要：示例輸入輸出輸入解釋相交節(jié)點(diǎn)的值為注意，如果兩個(gè)列表相交則不能為。解釋這兩個(gè)鏈表不相交，因此返回。注意如果兩個(gè)鏈表沒(méi)有交點(diǎn)，返回在返回結(jié)果后，兩個(gè)鏈表仍須保持原有的結(jié)構(gòu)。此時(shí)將指向鏈表長(zhǎng)鏈表的頭節(jié)點(diǎn)，不變。

愛(ài)寫(xiě)B(tài)ug（ID：iCodeBugs）

編寫(xiě)一個(gè)程序，找到兩個(gè)單鏈表相交的起始節(jié)點(diǎn)。

Write a program to find the node at which the intersection of two singly linked lists begins.

如下面的兩個(gè)鏈表：

在節(jié)點(diǎn) c1 開(kāi)始相交。

示例 1：

輸入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
輸出：Reference of the node with value = 8
輸入解釋：相交節(jié)點(diǎn)的值為 8 （注意，如果兩個(gè)列表相交則不能為 0）。從各自的表頭開(kāi)始算起，鏈表 A 為 [4,1,8,4,5]，鏈表 B 為 [5,0,1,8,4,5]。在 A 中，相交節(jié)點(diǎn)前有 2 個(gè)節(jié)點(diǎn)；在 B 中，相交節(jié)點(diǎn)前有 3 個(gè)節(jié)點(diǎn)。

示例 2：**

輸入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
輸出：Reference of the node with value = 2
輸入解釋：相交節(jié)點(diǎn)的值為 2 （注意，如果兩個(gè)列表相交則不能為 0）。從各自的表頭開(kāi)始算起，鏈表 A 為 [0,9,1,2,4]，鏈表 B 為 [3,2,4]。在 A 中，相交節(jié)點(diǎn)前有 3 個(gè)節(jié)點(diǎn)；在 B 中，相交節(jié)點(diǎn)前有 1 個(gè)節(jié)點(diǎn)。

示例 3：**

輸入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
輸出：null
輸入解釋：從各自的表頭開(kāi)始算起，鏈表 A 為 [2,6,4]，鏈表 B 為 [1,5]。由于這兩個(gè)鏈表不相交，所以 intersectVal 必須為 0，而 skipA 和 skipB 可以是任意值。
解釋：這兩個(gè)鏈表不相交，因此返回 null。

注意：

如果兩個(gè)鏈表沒(méi)有交點(diǎn)，返回 null.

在返回結(jié)果后，兩個(gè)鏈表仍須保持原有的結(jié)構(gòu)。

可假定整個(gè)鏈表結(jié)構(gòu)中沒(méi)有循環(huán)。

程序盡量滿足 O(_n_) 時(shí)間復(fù)雜度，且僅用 O(_1_) 內(nèi)存。 相交鏈表

Notes:

If the two linked lists have no intersection at all, return null.

The linked lists must retain their original structure after the function returns.

You may assume there are no cycles anywhere in the entire linked structure.

Your code should preferably run in O(n) time and use only O(1) memory.

解題思路：

注意：長(zhǎng)鏈表比短鏈表多出的長(zhǎng)度是無(wú)需比較的

剛開(kāi)始我是想著直接從兩個(gè)鏈表末尾向前遍歷對(duì)比節(jié)點(diǎn)是否相等，后面才看到是單鏈表。但是依然有很多的解題方法：

哈希表：把一個(gè)鏈表的節(jié)點(diǎn)先存儲(chǔ)在哈希表，遍歷另一個(gè)節(jié)點(diǎn)并判斷該節(jié)點(diǎn)地址是否在哈希表中出現(xiàn)過(guò)如果出現(xiàn)過(guò)，輸出該節(jié)點(diǎn)。需要占用額外空間 O(n)。

如果按要求在 O(1) 空間復(fù)雜度解題，最容易想到的就是：遍歷鏈表得到鏈表長(zhǎng)度，計(jì)算雙鏈表差值，長(zhǎng)鏈表減去差值得到的剩下的鏈表與短鏈表長(zhǎng)度相等，然后開(kāi)始比較地址。，當(dāng)遇到第一個(gè)節(jié)點(diǎn)地址相同時(shí)即為所求。

這個(gè)原理簡(jiǎn)單，但是代碼太冗長(zhǎng)了，我們來(lái)看另一種更優(yōu)雅的解法，看圖幫助理解：

定義兩個(gè)指針curA、curB分別從鏈表A、B開(kāi)始遍歷鏈表，此時(shí)最先遇到空節(jié)點(diǎn)(到達(dá)末尾)的鏈表即為短鏈表。

curA、curB走過(guò)的長(zhǎng)度均為L(zhǎng)enA。

此時(shí)將curA指向鏈表 B (長(zhǎng)鏈表)的頭節(jié)點(diǎn)，curB 不變。兩個(gè)指針開(kāi)始第二段遍歷，直到 curB 遇到空節(jié)點(diǎn)（長(zhǎng)鏈表到達(dá)末尾）。

此時(shí) curB 走完整個(gè)長(zhǎng)鏈表，走的第二段長(zhǎng)度就是差值 L。CurA 從長(zhǎng)鏈表頭節(jié)點(diǎn)開(kāi)始，與 curB 同步，其走的第二段長(zhǎng)度同樣是差值 L。

此時(shí) curA 在長(zhǎng)鏈表 剩余未遍歷的節(jié)點(diǎn)長(zhǎng)度是：LenB - L = LenA

此時(shí)將 curB 指向鏈表A的頭節(jié)點(diǎn)，即將遍歷鏈表A 的長(zhǎng)度為 LenA ，則curA、curB剩余即將遍歷的長(zhǎng)度即為原本需要比較的長(zhǎng)度。

開(kāi)始第三段遍歷，遇到第一個(gè)相同節(jié)點(diǎn)時(shí)返回即可。

代碼：

Java：

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode curA = headA;
        ListNode curB = headB;
        while (curA != curB) {
            curA = curA == null ? headB : curA.next;
            curB = curB == null ? headA : curB.next;
        }
        return curA;
    }
}

Python：

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        if not headA or not headB:
            return None
        curA , curB = headA , headB
        while curA != curB:
            curA = curA.next if curA else headB
            curB = curB.next if curB else headA
        return curA
歡迎關(guān)注公眾號(hào)一起學(xué)習(xí)：愛(ài)寫(xiě)B(tài)ug

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://specialneedsforspecialkids.com/yun/75477.html

相關(guān)文章

  • LeetCode 160： 相交鏈表 Intersection of Two Linked List

    摘要：示例輸入輸出輸入解釋相交節(jié)點(diǎn)的值為注意，如果兩個(gè)列表相交則不能為。解釋這兩個(gè)鏈表不相交，因此返回。注意如果兩個(gè)鏈表沒(méi)有交點(diǎn)，返回在返回結(jié)果后，兩個(gè)鏈表仍須保持原有的結(jié)構(gòu)。此時(shí)將指向鏈表長(zhǎng)鏈表的頭節(jié)點(diǎn)，不變。 愛(ài)寫(xiě)B(tài)ug（ID：iCodeBugs） 編寫(xiě)一個(gè)程序，找到兩個(gè)單鏈表相交的起始節(jié)點(diǎn)。 Write a program to find the node at which the i...

    ormsf 評(píng)論0 收藏0

  • 前端 | 每天一個(gè) LeetCode

    摘要：在線網(wǎng)站地址我的微信公眾號(hào)完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個(gè)題。這是項(xiàng)目地址歡迎一起交流學(xué)習(xí)。 這篇文章記錄我練習(xí)的 LeetCode 題目，語(yǔ)言 JavaScript。 在線網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號(hào)： showImg(htt...

    張漢慶 評(píng)論0 收藏0

  • LeetCode 攻略 - 2019 年 7 月下半月匯總（100 題攻略）

    摘要：月下半旬攻略道題，目前已攻略題。目前簡(jiǎn)單難度攻略已經(jīng)到題，所以后面會(huì)調(diào)整自己，在刷算法與數(shù)據(jù)結(jié)構(gòu)的同時(shí)，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。 一 目錄 不折騰的前端，和咸魚(yú)有什么區(qū)別...

    tain335 評(píng)論0 收藏0

  • LeetCode 攻略 - 2019 年 7 月上半月匯總（55 題攻略）

    摘要：微信公眾號(hào)記錄截圖記錄截圖目前關(guān)于這塊算法與數(shù)據(jù)結(jié)構(gòu)的安排前。已攻略返回目錄目前已攻略篇文章。會(huì)根據(jù)題解以及留言內(nèi)容，進(jìn)行補(bǔ)充，并添加上提供題解的小伙伴的昵稱和地址。本許可協(xié)議授權(quán)之外的使用權(quán)限可以從處獲得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一 目錄 不...

    warmcheng 評(píng)論0 收藏0

  • JAVASCRIPT算法（6）

    摘要：還是鏈表算法題目描述給出兩個(gè)無(wú)環(huán)單鏈表判斷和是否相交。所以可以得出另外一種解法，先遍歷鏈表，記住尾節(jié)點(diǎn)，然后遍歷鏈表，比較兩個(gè)鏈表的尾節(jié)點(diǎn)，如果相同則相交，不同則不相交。想法還是奇妙的。算法寫(xiě)起來(lái)不難，難的是想到這個(gè)。 還是鏈表算法 題目描述：給出兩個(gè)無(wú)環(huán)單鏈表A: a1 → a2 ↘ c1 → c2 → c3 → ...

    FreeZinG 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<