前言
想要精通算法和SQL的成長之路 - 系列導航
一. 相交鏈表（雙指針）
原題鏈接
思路如下：
1.我們假設 headA鏈表的長度為 a。headB鏈表的長度為b。兩個鏈表的公共部分長度為c（如果存在），公共節(jié)點為node。
- 頭結(jié)點
headA到node前，有a-c個節(jié)點。 - 頭結(jié)點
headB到node前，有b-c個節(jié)點。
2.那么我們用兩個指針，A和B。分別指向兩個鏈表的頭節(jié)點。
- 指針
A走完鏈表headA再走鏈表headB。走到node節(jié)點的時候，走過的步數(shù)為：a + (b - c) - 指針
B走完鏈表headB再走鏈表headA。走到node節(jié)點的時候，走過的步數(shù)為：b + (a - c)
首先，兩個指針走過的步數(shù)一定是相等的，但是對于返回結(jié)果而言，我們可以根據(jù)c來區(qū)分：文章來源：http://www.zghlxwxcb.cn/news/detail-733607.html
- 如果兩個鏈表存在相交鏈表，那么
c肯定非空，此時指針A或者B都是指向node節(jié)點。 - 如果兩個鏈表無相交部分，那么
c的值為0，也就是說此時A或者B的指向是null節(jié)點。
因此我們選哪個都可以，最后返回任意一個指針即可，代碼如下：文章來源地址http://www.zghlxwxcb.cn/news/detail-733607.html
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode a = headA, b = headB;
while (a != b) {
// 如果指針a為null，那么繼續(xù)遍歷headB鏈表，否則繼續(xù)遍歷headA鏈表。指針b同理
a = a == null ? headB : a.next;
b = b == null ? headA : b.next;
}
return a;
}
到了這里，關于想要精通算法和SQL的成長之路 - 相交鏈表的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
