輸入兩個鏈表，找出它們的第一個公共節(jié)點(diǎn)。
如下面的兩個鏈表：
在節(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 （注意瓷们，如果兩個列表相交則不能為 0）。從各自的表頭開始算起秒咐，鏈表 A 為 [4,1,8,4,5]谬晕，鏈表 B 為 [5,0,1,8,4,5]。在 A 中携取，相交節(jié)點(diǎn)前有 2 個節(jié)點(diǎn)攒钳；在 B 中，相交節(jié)點(diǎn)前有 3 個節(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 （注意不撑，如果兩個列表相交則不能為 0）。從各自的表頭開始算起惊豺，鏈表 A 為 [0,9,1,2,4]燎孟，鏈表 B 為 [3,2,4]。在 A 中尸昧，相交節(jié)點(diǎn)前有 3 個節(jié)點(diǎn)揩页；在 B 中，相交節(jié)點(diǎn)前有 1 個節(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]幢妄。由于這兩個鏈表不相交兔仰，所以 intersectVal 必須為 0，而 skipA 和 skipB 可以是任意值蕉鸳。
解釋：這兩個鏈表不相交乎赴，因此返回 null忍法。
注意：
如果兩個鏈表沒有交點(diǎn)，返回 null.
在返回結(jié)果后榕吼，兩個鏈表仍須保持原有的結(jié)構(gòu)饿序。
可假定整個鏈表結(jié)構(gòu)中沒有循環(huán)。
程序盡量滿足 O(n) 時間復(fù)雜度羹蚣，且僅用 O(1) 內(nèi)存原探。
本題與主站 160 題相同：https://leetcode-cn.com/problems/intersection-of-two-linked-lists/
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof
解題思路
本題在書中給出了兩種思路。
首先要明確的一點(diǎn)是顽素，如果兩個鏈表有交點(diǎn)咽弦，那么他們會形成一個Y字形，也就是相交之后的節(jié)點(diǎn)都是相交的胁出。
注意：相交的節(jié)點(diǎn)不是value相同型型，而是地址也要相同，所以不是A.val == B.val 而是 A == B
輔助棧划鸽， 這個想法比較直觀输莺，也是我想到的第一種方式戚哎，只遍歷兩個鏈表各一次裸诽，壓入棧中，這樣在出棧的時候就是從尾部開始遍歷型凳，找到最后一個相同的結(jié)點(diǎn)就是第一個相交的節(jié)點(diǎn)丈冬。這個做法有一個問題就是需要用額外的兩個棧空間甘畅。
書中給出的第二種思路埂蕊，即先得到兩個鏈表的長度，然后把較長的鏈表先走掉n-m步疏唾，之后兩個鏈表同時走蓄氧，比較之后是否有相同的節(jié)點(diǎn)，這個想法也比較直觀槐脏，但代碼量相對較長喉童，時間復(fù)雜度和空間復(fù)雜度都滿足要求。
這是我自己的解法顿天，有點(diǎn)臃腫...
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
int listALength = getListNodeLength(headA);
int listBLength = getListNodeLength(headB);
if (listALength > listBLength){
int step = listALength - listBLength;
headA = forwardStep(headA, step);
} else if (listALength < listBLength){
int step = listBLength - listALength;
headB = forwardStep(headB, step);
}
while(headA != null && headB != null && headA != headB){
headA = headA.next;
headB = headB.next;
}
return headA;
}
private int getListNodeLength(ListNode head){
int listLength = 0;
while(head != null){
listLength++;
head = head.next;
}
return listLength;
}
/*the longer list step forward n-m steps to make these
* two lists start and end at the same position
*/
private ListNode forwardStep(ListNode head, int step){
for(int i = 0; i < step; i++){
head = head.next;
}
return head;
}
}
- LeetCode論壇上的大神們給出一個相當(dāng)簡潔的做法堂氯，但思路需要理解一下，即雙指針法牌废。
假設(shè)相交的鏈表長度為c, A鏈表不相交部分為a, B鏈表不相交部分為b咽白，那么要滿足 a + c + b = b + c + a
偽代碼就是兩個指針同時從 A，B出發(fā)鸟缕，向后移動晶框，最先到達(dá)Null的指針指向另外一個鏈表的頭， 然后繼續(xù)后移。如果A, B 有交集一定會先交匯在第一個相同的節(jié)點(diǎn)上授段。
示例代碼
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null)
return null;
ListNode h1 = headA, h2 = headB;
while (h1 != h2) {
h1 = h1 == null ? headB : h1.next;
h2 = h2 == null ? headA : h2.next;
}
return h1;
}
