Leetcode - Intersection of Two Linked Lists

My code:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null)
            return null;
        int countA = 0;
        ListNode temp = headA;
        while (temp != null) {
            temp = temp.next;
            countA++;
        }
        int countB = 0;
        temp = headB;
        while (temp != null) {
            temp = temp.next;
            countB++;
        }
        
        int count = Math.abs(countA - countB);
        ListNode temp2 = null;
        if (countA > countB) {
            temp = headA;
            temp2 = headB;
        }
        else {
            temp = headB;
            temp2 = headA;
        }
        for (int i = 0; i < count; i++)
            temp =temp.next;
        
        while (temp != temp2) {
            temp = temp.next;
            temp2 = temp2.next;
        }
        return temp;
    }
}

My test result:

Paste_Image.png

這次題目是同學(xué)問我的寞肖,一開始有了思路哲身,但的確那個時候沒有考慮到一個細節(jié)辩涝。
什么是,交叉勘天。
就是兩個鏈表怔揩,在某一段開始,會首先公用一個結(jié)點脯丝。
那么之后呢商膊?
細節(jié)在這里。
nodeA = nodeB
兩個結(jié)點的引用地址是相同的巾钉,說明他們是一個結(jié)點翘狱,那么,接下來砰苍,他們的下一個結(jié)點潦匈。
nodeA.next = nodeB.next 也就是,下一個結(jié)點也是相同的赚导。一直往后茬缩。
也就是說,從交叉的那個結(jié)點開始吼旧,之后就不會再分開了凰锡。
一定要記住,交叉的點,是相同的掂为,是同一個結(jié)點裕膀,而不僅僅只是value相等。
然后思路就比較正常了勇哗。統(tǒng)計兩個鏈表的個數(shù)昼扛,然后讓長的先走一部分,然后開始和短的一起遍歷欲诺,判斷條件就是 nodeA == nodeB. 是等于抄谐。
另外,如果題目只是要求扰法,判斷兩個鏈表是否交叉蛹含。
可以將兩個鏈表相連,然后從后一個鏈表的頭開始遍歷塞颁,如果最后還可以回到頭部浦箱,那么就是交叉的。

**
總結(jié): LinkedList
**

Anyway, Good luck, Richardo!

My code:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        
        int totalA = 0;
        ListNode curr = headA;
        while (curr != null) {
            totalA++;
            curr = curr.next;
        }
        
        curr = headB;
        int totalB = 0;
        while (curr != null) {
            totalB++;
            curr = curr.next;
        }
        
        if (totalB > totalA) {
            int diff = totalB - totalA;
            while (diff > 0) {
                headB = headB.next;
                diff--;
            }
        }
        else if (totalB < totalA) {
            int diff = totalA - totalB;
            while (diff > 0) {
                headA = headA.next;
                diff--;
            }
        }
        
        while (headA != null && headB != null) {
            if (headA == headB) {
                return headA;
            }
            headA = headA.next;
            headB = headB.next;
        }
        
        return null;
    }
}

我的做法還是和以前差不多殴边。然后發(fā)現(xiàn)了另外一種神級的做法:
My code:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        
        ListNode a = headA;
        ListNode b = headB;
        while (a != b) {
            a = (a == null ? headB : a.next);
            b = (b == null ? headA : b.next);
        }
        
        return a;
    }
}

reference:
https://discuss.leetcode.com/topic/28067/java-solution-without-knowing-the-difference-in-len

太神奇的一種做法了憎茂,讓我想起了珍语, LinkedList Cycle 2
也是依靠計算距離差锤岸,最后達到我們需要的結(jié)果。

Anyway, Good luck, Richardo! -- 08/15/2016

如果 a,b 沒有交叉板乙,那么會陷入死循環(huán)是偷。

My code:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode p1 = headA;
        ListNode p2 = headB;
        int c1 = 0;
        int c2 = 0;
        while (p1 != p2) {
            p1 = p1.next;
            if (p1 == null) {
                p1 = headB;
                c1++;
                if (c1 > 1) {
                    return null;
                }
            }
            p2 = p2.next;
            if (p2 == null) {
                p2 = headA;
                c2++;
                if (c2 > 1) {
                    return null;
                }
            }
        }
        return p1;
    }
}

這個代碼可以解決這個問題。

Anyway, Good luck, Richardo! -- 09/25/2016

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末募逞,一起剝皮案震驚了整個濱河市蛋铆,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌放接,老刑警劉巖刺啦,帶你破解...
    沈念sama閱讀 222,729評論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異纠脾,居然都是意外死亡玛瘸,警方通過查閱死者的電腦和手機,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,226評論 3 399
  • 文/潘曉璐 我一進店門苟蹈,熙熙樓的掌柜王于貴愁眉苦臉地迎上來糊渊,“玉大人,你說我怎么就攤上這事慧脱∶烊蓿” “怎么了?”我有些...
    開封第一講書人閱讀 169,461評論 0 362
  • 文/不壞的土叔 我叫張陵,是天一觀的道長宗兼。 經(jīng)常有香客問我躏鱼,道長,這世上最難降的妖魔是什么殷绍? 我笑而不...
    開封第一講書人閱讀 60,135評論 1 300
  • 正文 為了忘掉前任挠他,我火速辦了婚禮,結(jié)果婚禮上篡帕,老公的妹妹穿的比我還像新娘殖侵。我一直安慰自己,他們只是感情好镰烧,可當(dāng)我...
    茶點故事閱讀 69,130評論 6 398
  • 文/花漫 我一把揭開白布拢军。 她就那樣靜靜地躺著,像睡著了一般怔鳖。 火紅的嫁衣襯著肌膚如雪茉唉。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 52,736評論 1 312
  • 那天结执,我揣著相機與錄音度陆,去河邊找鬼。 笑死献幔,一個胖子當(dāng)著我的面吹牛懂傀,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播蜡感,決...
    沈念sama閱讀 41,179評論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼蹬蚁,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了郑兴?” 一聲冷哼從身側(cè)響起犀斋,我...
    開封第一講書人閱讀 40,124評論 0 277
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎情连,沒想到半個月后叽粹,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 46,657評論 1 320
  • 正文 獨居荒郊野嶺守林人離奇死亡却舀,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,723評論 3 342
  • 正文 我和宋清朗相戀三年虫几,在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片禁筏。...
    茶點故事閱讀 40,872評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡持钉,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出篱昔,到底是詐尸還是另有隱情每强,我是刑警寧澤始腾,帶...
    沈念sama閱讀 36,533評論 5 351
  • 正文 年R本政府宣布,位于F島的核電站空执,受9級特大地震影響浪箭,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜辨绊,卻給世界環(huán)境...
    茶點故事閱讀 42,213評論 3 336
  • 文/蒙蒙 一奶栖、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧门坷,春花似錦宣鄙、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,700評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至绸吸,卻和暖如春鼻弧,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背锦茁。 一陣腳步聲響...
    開封第一講書人閱讀 33,819評論 1 274
  • 我被黑心中介騙來泰國打工攘轩, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留,地道東北人码俩。 一個月前我還...
    沈念sama閱讀 49,304評論 3 379
  • 正文 我出身青樓度帮,卻偏偏與公主長得像,于是被迫代替她去往敵國和親握玛。 傳聞我的和親對象是個殘疾皇子够傍,可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 45,876評論 2 361

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

  • My code: 這道題目不難甫菠,但是很煩挠铲。自己也沒能做出來。剛剛才分析過插入排序的寂诱,但是一旦涉及到鏈表拂苹,就好復(fù)雜。...
    Richardo92閱讀 469評論 0 1
  • My code: My test result: 這道題目我一開始想用異或來做痰洒,后來發(fā)現(xiàn)錯的瓢棒,即使一個數(shù)字出現(xiàn)了偶...
    Richardo92閱讀 401評論 0 1
  • My code: My test result: 這道題目一開始理解錯題意了。丘喻。真是啃爹脯宿。然后,以前反轉(zhuǎn)鏈表泉粉,我都...
    Richardo92閱讀 332評論 0 1
  • My code: My test result: 這次作業(yè)說實話不難连霉,但是要完全寫出來還是有點細節(jié)的榴芳。首先,一開始...
    Richardo92閱讀 458評論 1 1
  • Justina_Fu閱讀 167評論 0 0