😈博客主頁：🐼大家好我叫張同學🐼
💖 歡迎點贊 👍 收藏 💗留言 📝 歡迎討論！ 👀
🎵本文由 【大家好我叫張同學】 原創，首發于 CSDN 🌟🌟🌟
?精品專欄（不定時更新） 【資料結構+演算法】 【做題筆記】【C語言編程學習】
?? 精品文章推薦
【C語言進階學習筆記】三、字串函式詳解（1）（爆肝吐血整理，建議收藏！！！）
【C語言基礎學習筆記】+【C語言進階學習筆記】總結篇（堅持才有識訓！）
| 前言 |
為什么要寫
刷題筆記？
寫博客的程序也是對自己刷題程序的梳理和總結，是一種耗時但有效的方法，
當自己分享的博客幫助到他人時，又會給自己帶來額外的快樂和幸福，
（刷題的快樂+博客的快樂，簡直是獎勵翻倍，快樂翻倍有木有QAQ🙈）
| 題目內容 |
給你兩個單鏈表的頭節點
headA和headB，請你找出并回傳兩個單鏈表相交的起始節點，如果兩個鏈表不存在相交節點，回傳null，
圖示兩個鏈表在節點 c1 開始相交：
題目資料
保證整個鏈式結構中不存在環，
注意，函式回傳結果后，鏈表必須保持其原始結構 ，
自定義評測： 評測系統的輸入如下（你設計的程式不適用此輸入）：
intersectVal- 相交的起始節點的值，如果不存在相交節點，這一值為 0
listA第一個鏈表
listB- 第二個鏈表
skipA- 在listA中（從頭節點開始）跳到交叉節點的節點數
skipB- 在listB中（從頭節點開始）跳到交叉節點的節點數
評測系統將根據這些輸入創建鏈式資料結構，并將兩個頭節點headA和headB傳遞給你的程式，如果程式能夠正確回傳相交節點，那么你的解決方案將被 視作正確答案 ，
原題鏈接（點擊跳轉）
| 暴力求解法 |
理解相交：不是指A鏈表中有和B鏈表中val值相同的結點，而是指這個兩個鏈表中存在相同的結點，如果我們通過指標去遍歷A、B兩個鏈表，能夠在A、B中找到相同地址的結點，那A、B相交，否則就是不相交，
| 函式實作 |
每次從
A鏈表中取一個結點去跟B鏈表中所有結點進行比較，看是否存在相同的結點，若存在則回傳相交結點，否則回傳NULL（不相交），
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
struct ListNode *curA = headA,*curB = headB;
while(curA){
curB = headB;
while(curB){
if(curB == curA)
return curB;
curB = curB->next;
}
curA = curA->next;
}
return NULL;
}
| 手拉手一起走 |
這種方式的時間復雜度為O(n^2)，空間復雜度是O(1)，那能不能想辦法改進，降低時間復雜度呢？最好是能實作O(m+n) time，O(1) memory，
其實要判斷兩個鏈表是否相交很簡單，我們可以直接判斷兩個鏈表的最后一個結點是否相同，若相同則肯定相交，否則就不相交，
但比較麻煩的是我們還需要回傳相交的結點，為了實作這個要求，我們可以再遍歷A、B兩個鏈表找最后一個結點的時候求A、B的長度lenA、lenB，之后讓A、B鏈表中較長的先走 step = | lenA - lenB |(| |表示絕對值）步，然后兩個再一起往下走，遇到的第一個相同的結點即為相交結點，
| 函式實作 |
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
if(headA == NULL || headB == NULL)
return NULL;
//判斷相交，僅需判斷最后一個結點是否相同
struct ListNode *curA = headA,*curB = headB;
int lenA = 1,lenB = 1;
while(curA && curA->next){
lenA++;
curA = curA->next;
}
while(curB && curB->next){
lenB++;
curB = curB->next;
}
curA = headA;
curB = headB;
if(lenA > lenB){
int step = lenA - lenB;
while(step--){
curA = curA->next;
}
}
else if(lenB > lenA){
int step = lenB - lenA;
while(step--){
curB = curB->next;
}
}
while(curA != curB){
curA = curA->next;
curB = curB->next;
}
return curA;
}
| 利用數學知識 |
除了剛剛說的思路外，我們也可不用求A、B鏈表的長度來實作回傳相交結點的目的，不過這種方式需要一點點的數學技巧，
| 函式實作 |
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
struct ListNode *curA = headA,*curB = headB;
while(curA != curB){
curA = curA == NULL ? headB : curA->next;
curB = curB == NULL ? headA : curB->next;
}
return curA;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/413959.html
標籤：其他
下一篇：演算法篇：1、演算法起源