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:
这次题目是同学问我的，一开始有了思路，但的确那个时候没有考虑到一个细节。
什么是，交叉。
就是两个链表，在某一段开始，会首先公用一个结点。
那么之后呢？
细节在这里。
nodeA = nodeB
两个结点的引用地址是相同的，说明他们是一个结点，那么，接下来，他们的下一个结点。
nodeA.next = nodeB.next 也就是，下一个结点也是相同的。一直往后。
也就是说，从交叉的那个结点开始，之后就不会再分开了。
一定要记住，交叉的点，是相同的，是同一个结点，而不仅仅只是value相等。
然后思路就比较正常了。统计两个链表的个数，然后让长的先走一部分，然后开始和短的一起遍历，判断条件就是 nodeA == nodeB. 是等于。
另外，如果题目只是要求，判断两个链表是否交叉。
可以将两个链表相连，然后从后一个链表的头开始遍历，如果最后还可以回到头部，那么就是交叉的。
**
总结： 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;
}
}
我的做法还是和以前差不多。然后发现了另外一种神级的做法：
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
也是依靠计算距离差，最后达到我们需要的结果。
Anyway, Good luck, Richardo! -- 08/15/2016
如果 a,b 没有交叉，那么会陷入死循环。
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
