更詳細(xì)的講解和代碼調(diào)試演示過程蹬挺，請(qǐng)參看視頻
如何進(jìn)入google,算法面試技能全面提升指南
給定兩個(gè)單向鏈表，這兩個(gè)鏈表有可能會(huì)有重疊它掂，情況如下：
兩個(gè)單向鏈表從節(jié)點(diǎn)5開始重合巴帮，要求給定一個(gè)空間復(fù)雜度為O(1)的算法，返回兩個(gè)鏈表相交時(shí)的第一個(gè)節(jié)點(diǎn)虐秋。依據(jù)上圖榕茧，也就是返回節(jié)點(diǎn)5.
首先我們需要做的是，確保給定的兩個(gè)單向鏈表客给，他們是相交的用押。這個(gè)很好確定，只要從頭遍歷兩個(gè)鏈表靶剑，如果他們的尾節(jié)點(diǎn)是一樣的話蜻拨，那么這兩個(gè)鏈表就是相交的池充，問題是，如何盡快找到他們相交的第一個(gè)節(jié)點(diǎn)缎讼。
最笨的辦法是收夸，先找到尾節(jié)點(diǎn)，然后去掉尾節(jié)點(diǎn)血崭，然后再次遍歷查找新的尾節(jié)點(diǎn)卧惜，然后再去掉，直到兩個(gè)鏈表沒有共同的尾節(jié)點(diǎn)夹纫，那么最后去掉的共同尾巴節(jié)點(diǎn)咽瓷，則是兩個(gè)鏈表的首次相交節(jié)點(diǎn)。這種做法可行舰讹，但是算法復(fù)雜度是O(n^2)茅姜。有沒有更好的辦法呢？
假設(shè)第一個(gè)鏈表跺涤，從頭結(jié)點(diǎn)到首次相交節(jié)點(diǎn)匈睁，所經(jīng)歷的距離用T1來表示，根據(jù)上圖例子桶错，T1 = 5, 也就是第一個(gè)隊(duì)列從頭結(jié)點(diǎn)0開始航唆，需要經(jīng)歷節(jié)點(diǎn)1，2院刁，3糯钙，4也就是總共5個(gè)節(jié)點(diǎn)后才能到達(dá)節(jié)點(diǎn)5.
我們用T3 表示隊(duì)列2從頭節(jié)點(diǎn)開始，到達(dá)首次相交節(jié)點(diǎn)的距離退腥。根據(jù)上圖任岸，T3 = 3.
我們用T2表示兩隊(duì)列相交部分的節(jié)點(diǎn)數(shù).依據(jù)上圖T2 = 5.
由此隊(duì)列1的長(zhǎng)度為： T1 + T2 (1)
隊(duì)列2的長(zhǎng)度為：T3 + T2 (2)
如果我們能算出T3的數(shù)值，那么我們從隊(duì)列2的頭結(jié)點(diǎn)出發(fā)狡刘，經(jīng)過T3-1步后享潜，就能達(dá)到首次相交節(jié)點(diǎn)。我們?nèi)绾斡?jì)算T3的數(shù)值呢嗅蔬？
對(duì)T3的計(jì)算剑按，需要一個(gè)小技巧.我們把隊(duì)列2進(jìn)行反轉(zhuǎn)，得到下面情形：
如果此時(shí)我們從隊(duì)列1的頭結(jié)點(diǎn)開始進(jìn)行遍歷澜术，那么從上頭的節(jié)點(diǎn)0開始出發(fā)艺蝴，會(huì)到隊(duì)列2的頭結(jié)點(diǎn)0結(jié)束。這樣鸟废，在反轉(zhuǎn)后猜敢，如果再次從頭遍歷隊(duì)列1的話，得到的長(zhǎng)度就是：
T1 + T3 + 1 (3).
根據(jù)上面三個(gè)公式，我們便可以計(jì)算出T3來缩擂。
(3) - (1) = T1 + T3 + 1 - T1 - T2 = T3 - T2 + 1
(3) - (1) + (2) = T3 - T2 + 1 + T3 + T2 = 2*T3 + 1
由此鼠冕，我們可以反解出T3, 有了T3，我們便可以得到兩隊(duì)列首次相交節(jié)點(diǎn)了撇叁。
這個(gè)算法除了需要遍歷兩個(gè)隊(duì)列外供鸠，還需要對(duì)其中一個(gè)隊(duì)列進(jìn)行反轉(zhuǎn)畦贸，無論是遍歷還是反轉(zhuǎn)陨闹，其算法復(fù)雜度都是O(n), 因此總算法復(fù)雜度是O(n).
代碼實(shí)現(xiàn)：
public class ListIntersetChecker {
private Node listHead1;
private Node listHead2;
private int firstListLen = 0; //t1 + t2
private int secondListLen = 0; // t3 + t2
private int lenAfterReverse = 0; // t1 + t3
private ListReverse listReverse = null;
public ListIntersetChecker(Node listHead1, Node listHead2) {
this.listHead1 = listHead1;
this.listHead2 = listHead2;
}
public Node getFirstIntersetNode() {
if (isTwoListInterset() == false) {
return null;
}
listReverse = new ListReverse(listHead2);
Node reverseHead = listReverse.getReverseList();
lenAfterReverse = getListLen(listHead1);
int t3 = ((lenAfterReverse - firstListLen) + secondListLen - 1) / 2;
int steps = secondListLen - t3 - 1;
while (steps > 0) {
reverseHead = reverseHead.next;
steps--;
}
return reverseHead;
}
private int getListLen(Node head) {
int len = 0;
while (head != null) {
head = head.next;
len++;
}
return len;
}
private boolean isTwoListInterset() {
Node head1 = listHead1;
Node head2 = listHead2;
while (head1.next != null || head2.next != null) {
if (head1.next != null) {
head1 = head1.next;
firstListLen++;
}
if (head2.next != null) {
head2 = head2.next;
secondListLen++;
}
}
firstListLen++;
secondListLen++;
return head1 == head2;
}
}
ListIntersetCheck.java 用于實(shí)現(xiàn)上面描述的算法。 getFirstIntersetNode返回兩重疊隊(duì)列首次相交節(jié)點(diǎn)薄坏。isTwoListInterset 用于判斷兩隊(duì)列是否相交趋厉。在遍歷兩隊(duì)列時(shí)，統(tǒng)計(jì)兩隊(duì)列的長(zhǎng)度胶坠，也就是獲得 T1 + T2 以及 T3 + T2的值君账。
然后把隊(duì)列2進(jìn)行反轉(zhuǎn)，反轉(zhuǎn)后沈善，再從隊(duì)列1的頭節(jié)點(diǎn)進(jìn)行遍歷乡数，得到的lenAfterReverse就是 T1 + T3 + 1.
int t3 = ((lenAfterReverse - firstListLen) + secondListLen - 1) / 2;
上面語句則根據(jù)前面的推導(dǎo)計(jì)算出T3.
由于隊(duì)列2已經(jīng)反轉(zhuǎn)了，所以不能從隊(duì)列2的頭結(jié)點(diǎn)去遍歷闻牡，只能從隊(duì)列2的尾節(jié)點(diǎn)開始遍歷净赴，如果頭結(jié)點(diǎn)開始遍歷需要T3步的話，那么從尾節(jié)點(diǎn)遍歷罩润，則需要steps = secondListLen - (T3 + 1) 步玖翅。
由此，代碼從隊(duì)列2反轉(zhuǎn)后的頭結(jié)點(diǎn)開始割以，經(jīng)過steps個(gè)節(jié)點(diǎn)后抵達(dá)兩隊(duì)列首次相交時(shí)的節(jié)點(diǎn)金度。
再看看主入口代碼:
public class LinkList {
public static void main(String[] args) {
ListUtility util1 = new ListUtility();
ListUtility util2 = new ListUtility();
Node list1 = util1.createList(10);
Node list2 = util2.createList(3);
Node node = util1.getNodeByIdx(5);
Node tail = util2.getNodeByIdx(2);
tail.next = node;
ListIntersetChecker intersetChecker = new ListIntersetChecker(list1, list2);
Node interset = intersetChecker.getFirstIntersetNode();
System.out.println("The first interset node is : " + interset.val);
}
}
程序啟動(dòng)時(shí)，先構(gòu)造兩個(gè)隊(duì)列严沥，隊(duì)列1節(jié)點(diǎn)從0到9猜极，隊(duì)列2從0到2，然后把隊(duì)列2的尾節(jié)點(diǎn)的next指向隊(duì)列1的編號(hào)為5的節(jié)點(diǎn)消玄，于是就構(gòu)造了我們例子圖中的兩個(gè)相交隊(duì)列跟伏，然后再利用ListIntersetChecker獲得兩重合隊(duì)列的首個(gè)相交節(jié)點(diǎn)。
最后程序運(yùn)行結(jié)果為：
The first interset node is : 5
結(jié)果跟我們理論推導(dǎo)一致莱找，也就是說酬姆，我們的說法實(shí)現(xiàn)是正確的。更詳細(xì)的代碼講解和推導(dǎo)調(diào)試過程奥溺，請(qǐng)參看視頻辞色。
更多技術(shù)信息，包括操作系統(tǒng)浮定，編譯器相满，面試算法层亿，機(jī)器學(xué)習(xí)，人工智能立美，請(qǐng)關(guān)照我的公眾號(hào)：
