LeetCode 每日一題160: 相交鏈表

leetcode.png

題目

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

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

在節(jié)點(diǎn) c1 開始相交蹬碧。

示例 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)。從各自的表頭開始算起坠七,鏈表 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)。從各自的表頭開始算起的猛,鏈表 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
輸入解釋:從各自的表頭開始算起忿薇,鏈表 A 為 [2,6,4],鏈表 B 為 [1,5]躏哩。由于這兩個(gè)鏈表不相交署浩,所以 intersectVal 必須為 0,而 skipA 和 skipB 可以是任意值扫尺。
解釋:這兩個(gè)鏈表不相交筋栋,因此返回 null。

注意:

  • 如果兩個(gè)鏈表沒有交點(diǎn)正驻,返回 null.
  • 在返回結(jié)果后弊攘,兩個(gè)鏈表仍須保持原有的結(jié)構(gòu)抢腐。
  • 可假定整個(gè)鏈表結(jié)構(gòu)中沒有循環(huán)。
  • 程序盡量滿足 O(n) 時(shí)間復(fù)雜度襟交,且僅用 O(1) 內(nèi)存迈倍。

數(shù)據(jù)結(jié)構(gòu)定義

C

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

Python

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

思路

今天這道題的兩個(gè)思路本質(zhì)上都是鏈表的規(guī)整.

獲取鏈表長度實(shí)現(xiàn)規(guī)整

這是最容易想到的一種方法,直接遍歷獲取兩個(gè)鏈表的長度. 獲得二者的長度差, 長鏈表先走差值對應(yīng)的步數(shù), 然后兩個(gè)鏈表同時(shí)前進(jìn), 實(shí)現(xiàn)鏈表規(guī)整的目的. 耗時(shí)為兩次循環(huán), 即O(n)的常數(shù)倍.

C實(shí)現(xiàn)

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    if(!headA || !headB)
        return NULL;
    struct ListNode *a = headA;
    struct ListNode *b = headB;
    int lenA = 0, lenB = 0;
    int fast = 0;
    while(a){
        a = a->next;
        lenA++;
    }
    while(b){
        b = b->next;
        lenB++;
    }
    fast = lenA>lenB ? (lenA-lenB) : (lenB-lenA);
    while(fast--){
        if(lenA-lenB > 0){
            headA = headA->next;
        }
        else{
            headB = headB->next;
        }
    }
    
    while(headA && headB){
        if(headA == headB)
            return headA;
        headA = headA->next;
        headB = headB->next;
    }
    return NULL;
}

![結(jié)果](https://upload-images.jianshu.io/upload_images/5530017-a07041f7c0c4651b.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)


Python實(shí)現(xiàn)

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        lenA = 0
        a = headA
        b = headB
        while a:
            a = a.next
            lenA += 1
        lenB = 0
        while b:
            b = b.next
            lenB += 1
        fast = abs(lenA-lenB)
        if lenA - lenB > 0:
            while fast > 0: 
                headA = headA.next
                fast -= 1
        else:
            while fast > 0:
                headB = headB.next
                fast -= 1
        while headA and headB:
            if headA == headB:
                return headA
            headA = headA.next
            headB = headB.next
        return None
結(jié)果

鏈表拼接實(shí)現(xiàn)規(guī)整

這是一種較為巧妙的實(shí)現(xiàn)方式, 思路來自評論區(qū)的大佬. 設(shè)置兩個(gè)指針, 指向兩個(gè)鏈表的表頭, 二者同時(shí)前進(jìn), 到達(dá)鏈表尾則將指針指向另一個(gè)鏈表, 此時(shí)兩個(gè)鏈表便實(shí)現(xiàn)規(guī)整; 繼續(xù)前進(jìn), 若有相交則返回節(jié)點(diǎn), 否則遍歷長度為二者的長度之和.

如果你仍覺得不好理解, 請動(dòng)手模擬下面的示例, 將兩個(gè)鏈表拼接在一起, 是不是有豁然開朗的感覺?

示例

C實(shí)現(xiàn)

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    if (!headA || !headB)
        return NULL;
    struct ListNode *a = headA;
    struct ListNode *b = headB;
    while(a != b){
        a = a ? a->next : headB;
        b = b ? b->next : headA;
    }
    return a;
}
result

Python實(shí)現(xiàn)

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        if not headA  or not headB:
            return None
        a,b = headA, headB  
        while a != b:
            a = a.next if a else headB
            b = b.next if b else headA
        return a
結(jié)果

微信公眾號: 程序員的碎碎念

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市捣域,隨后出現(xiàn)的幾起案子啼染,更是在濱河造成了極大的恐慌,老刑警劉巖竟宋,帶你破解...
    沈念sama閱讀 222,378評論 6 516
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件提完,死亡現(xiàn)場離奇詭異,居然都是意外死亡丘侠,警方通過查閱死者的電腦和手機(jī)徒欣,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 94,970評論 3 399
  • 文/潘曉璐 我一進(jìn)店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來蜗字,“玉大人打肝,你說我怎么就攤上這事∨膊叮” “怎么了粗梭?”我有些...
    開封第一講書人閱讀 168,983評論 0 362
  • 文/不壞的土叔 我叫張陵,是天一觀的道長级零。 經(jīng)常有香客問我断医,道長,這世上最難降的妖魔是什么奏纪? 我笑而不...
    開封第一講書人閱讀 59,938評論 1 299
  • 正文 為了忘掉前任鉴嗤,我火速辦了婚禮,結(jié)果婚禮上序调,老公的妹妹穿的比我還像新娘醉锅。我一直安慰自己,他們只是感情好发绢,可當(dāng)我...
    茶點(diǎn)故事閱讀 68,955評論 6 398
  • 文/花漫 我一把揭開白布硬耍。 她就那樣靜靜地躺著,像睡著了一般边酒。 火紅的嫁衣襯著肌膚如雪经柴。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 52,549評論 1 312
  • 那天墩朦,我揣著相機(jī)與錄音口锭,去河邊找鬼。 笑死介杆,一個(gè)胖子當(dāng)著我的面吹牛鹃操,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播春哨,決...
    沈念sama閱讀 41,063評論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼荆隘,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了赴背?” 一聲冷哼從身側(cè)響起椰拒,我...
    開封第一講書人閱讀 39,991評論 0 277
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎凰荚,沒想到半個(gè)月后燃观,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 46,522評論 1 319
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡便瑟,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,604評論 3 342
  • 正文 我和宋清朗相戀三年缆毁,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片到涂。...
    茶點(diǎn)故事閱讀 40,742評論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡脊框,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出践啄,到底是詐尸還是另有隱情浇雹,我是刑警寧澤,帶...
    沈念sama閱讀 36,413評論 5 351
  • 正文 年R本政府宣布屿讽,位于F島的核電站昭灵,受9級特大地震影響,放射性物質(zhì)發(fā)生泄漏伐谈。R本人自食惡果不足惜烂完,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,094評論 3 335
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望衩婚。 院中可真熱鬧窜护,春花似錦、人聲如沸非春。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,572評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽奇昙。三九已至护侮,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間储耐,已是汗流浹背羊初。 一陣腳步聲響...
    開封第一講書人閱讀 33,671評論 1 274
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人长赞。 一個(gè)月前我還...
    沈念sama閱讀 49,159評論 3 378
  • 正文 我出身青樓晦攒,卻偏偏與公主長得像,于是被迫代替她去往敵國和親得哆。 傳聞我的和親對象是個(gè)殘疾皇子脯颜,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,747評論 2 361

推薦閱讀更多精彩內(nèi)容