個(gè)人企業(yè)網(wǎng)站怎么建設(shè)seo外鏈資源
原題鏈接:https://leetcode.cn/problems/intersection-of-two-linked-lists/description/
目錄
1. 題目描述
2. 思路分析
3. 代碼實(shí)現(xiàn)
1. 題目描述
?
2. 思路分析
看到這道題,很容易想到的方法就是暴力求解,就是將一個(gè)鏈表的每個(gè)結(jié)點(diǎn)的地址分別和另外一個(gè)鏈表的每個(gè)結(jié)點(diǎn)的地址進(jìn)行比較,如果有相等的,就說明相交了。(注意這里不能比值,因?yàn)閮蓚€(gè)不同的結(jié)點(diǎn)值有可能一樣)。但是這樣的時(shí)間復(fù)雜度太高了,為O(N^2)。
這道題有一個(gè)很好的做法:
先計(jì)算出兩個(gè)鏈表的長度,讓長的鏈表先走相差的長度,然后兩個(gè)鏈表同時(shí)走,直到遇到相同的結(jié)點(diǎn),即為第一個(gè)公共結(jié)點(diǎn)。
我們定義了四個(gè)變量curA,curB,lenA,lenB。
我們用結(jié)構(gòu)體指針curA遍歷鏈表A,用結(jié)構(gòu)體指針curB遍歷鏈表B。
lenA表示鏈表A的長度,lenB表示鏈表B的長度。
用while循環(huán)通過遍歷分別得到了鏈表A和B的長度。
我們判斷尾結(jié)點(diǎn)是否相等,如果尾結(jié)點(diǎn)相等,說明兩個(gè)鏈表一定相交!!!
(我們看下圖,如果兩個(gè)鏈表相交,那么從這個(gè)相交的結(jié)點(diǎn)(包括這個(gè)交點(diǎn))之后的結(jié)點(diǎn),在兩個(gè)鏈表中都是相等的。所以尾結(jié)點(diǎn)相等,說明兩個(gè)鏈表一定相交。)
如果兩個(gè)鏈表不相交(curA!=curB),我們直接返回空指針NULL。
如果兩個(gè)鏈表相交,我們先讓長的鏈表走兩個(gè)鏈表長度的差距步(gap)。因?yàn)椴恢纼蓚€(gè)鏈表哪個(gè)長,所以我們使用了abs()函數(shù),差距步gap就是abs(lenA-lenB)。
之后我們又引入了兩個(gè)結(jié)構(gòu)體指針longList和shortList分別指向長鏈表和短鏈表的頭。這里用了if語句判斷,先假設(shè)某個(gè)鏈表是長鏈表,如果不是,就讓它等于短鏈表。
然后我們用一個(gè)while循環(huán)讓長鏈表走差距步(while(gap--))。
然后讓longList和shortList這兩個(gè)結(jié)構(gòu)體指針同時(shí)走,找交點(diǎn),找到交點(diǎn)時(shí)結(jié)束循環(huán)。
最后返回longList即可。
3. 代碼實(shí)現(xiàn)
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode *curA=headA,*curB=headB;int lenA=1,lenB=1;//計(jì)算鏈表長度while(curA->next){curA=curA->next; ++lenA;}while(curB->next){curB=curB->next;++lenB;}//不相交if(curA!=curB)return NULL;int gap=abs(lenA-lenB);struct ListNode *longList=headA,*shortList=headB;if(lenA<lenB){longList=headB;shortList=headA;}//長的先走差距步while(gap--){longList=longList->next;}//同時(shí)走找交點(diǎn)while(longList!=shortList){longList=longList->next;shortList=shortList->next;}return longList;
}
?