My code:
/**
* 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) {
if (headA == null || headB == null)
return null;
int countA = 0;
ListNode temp = headA;
while (temp != null) {
temp = temp.next;
countA++;
}
int countB = 0;
temp = headB;
while (temp != null) {
temp = temp.next;
countB++;
}
int count = Math.abs(countA - countB);
ListNode temp2 = null;
if (countA > countB) {
temp = headA;
temp2 = headB;
}
else {
temp = headB;
temp2 = headA;
}
for (int i = 0; i < count; i++)
temp =temp.next;
while (temp != temp2) {
temp = temp.next;
temp2 = temp2.next;
}
return temp;
}
}
My test result:
這次題目是同學(xué)問我的寞肖，一開始有了思路哲身，但的確那個時候沒有考慮到一個細節(jié)辩涝。
什么是，交叉勘天。
就是兩個鏈表怔揩，在某一段開始，會首先公用一個結(jié)點脯丝。
那么之后呢商膊？
細節(jié)在這里。
nodeA = nodeB
兩個結(jié)點的引用地址是相同的巾钉，說明他們是一個結(jié)點翘狱，那么，接下來砰苍，他們的下一個結(jié)點潦匈。
nodeA.next = nodeB.next 也就是，下一個結(jié)點也是相同的赚导。一直往后茬缩。
也就是說，從交叉的那個結(jié)點開始吼旧，之后就不會再分開了凰锡。
一定要記住，交叉的點，是相同的掂为，是同一個結(jié)點裕膀，而不僅僅只是value相等。
然后思路就比較正常了勇哗。統(tǒng)計兩個鏈表的個數(shù)昼扛，然后讓長的先走一部分，然后開始和短的一起遍歷欲诺，判斷條件就是 nodeA == nodeB. 是等于抄谐。
另外，如果題目只是要求扰法，判斷兩個鏈表是否交叉蛹含。
可以將兩個鏈表相連，然后從后一個鏈表的頭開始遍歷塞颁，如果最后還可以回到頭部浦箱，那么就是交叉的。
**
總結(jié)： LinkedList
**
Anyway, Good luck, Richardo!
My code:
/**
* 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) {
if (headA == null || headB == null) {
return null;
}
int totalA = 0;
ListNode curr = headA;
while (curr != null) {
totalA++;
curr = curr.next;
}
curr = headB;
int totalB = 0;
while (curr != null) {
totalB++;
curr = curr.next;
}
if (totalB > totalA) {
int diff = totalB - totalA;
while (diff > 0) {
headB = headB.next;
diff--;
}
}
else if (totalB < totalA) {
int diff = totalA - totalB;
while (diff > 0) {
headA = headA.next;
diff--;
}
}
while (headA != null && headB != null) {
if (headA == headB) {
return headA;
}
headA = headA.next;
headB = headB.next;
}
return null;
}
}
我的做法還是和以前差不多殴边。然后發(fā)現(xiàn)了另外一種神級的做法：
My code:
/**
* 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) {
if (headA == null || headB == null) {
return null;
}
ListNode a = headA;
ListNode b = headB;
while (a != b) {
a = (a == null ? headB : a.next);
b = (b == null ? headA : b.next);
}
return a;
}
}
reference:
https://discuss.leetcode.com/topic/28067/java-solution-without-knowing-the-difference-in-len
太神奇的一種做法了憎茂，讓我想起了珍语， LinkedList Cycle 2
也是依靠計算距離差锤岸，最后達到我們需要的結(jié)果。
Anyway, Good luck, Richardo! -- 08/15/2016
如果 a,b 沒有交叉板乙，那么會陷入死循環(huán)是偷。
My code:
/**
* 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) {
if (headA == null || headB == null) {
return null;
}
ListNode p1 = headA;
ListNode p2 = headB;
int c1 = 0;
int c2 = 0;
while (p1 != p2) {
p1 = p1.next;
if (p1 == null) {
p1 = headB;
c1++;
if (c1 > 1) {
return null;
}
}
p2 = p2.next;
if (p2 == null) {
p2 = headA;
c2++;
if (c2 > 1) {
return null;
}
}
}
return p1;
}
}
這個代碼可以解決這個問題。
Anyway, Good luck, Richardo! -- 09/25/2016
