題目
編寫一個(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;
}

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
鏈表拼接實(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;
}
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
微信公眾號: 程序員的碎碎念