編寫一個程序火窒，找到兩個單鏈表相交的起始節(jié)點(diǎn)版扩。
如下面的兩個鏈表：
在節(jié)點(diǎn) c1 開始相交鸡挠。
題解
java代碼如下
/**
* 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 lenA = 0;
int lenB = 0;
int gap = 0;
ListNode pA = headA;
ListNode pB = headB;
while(pA != null) {
lenA++;
pA = pA.next;
}
while(pB != null) {
lenB++;
pB = pB.next;
}
pA = headA;
pB = headB;
if (lenA < lenB) {
gap = lenB - lenA;
while(gap > 0) {
pB = pB.next;
gap--;
}
} else {
gap = lenA - lenB;
while(gap > 0) {
pA = pA.next;
gap--;
}
}
while(pA != null && pB != null) {
if(pA == pB) {
return pA;
}
pA = pA.next;
pB = pB.next;
}
return null;
}
}
