Write a program to find the node at which the intersection of two singly linked lists begins.
For example, the following two linked lists:
A: a1 → a2
↘
c1 → c2 → c3
↗
B: b1 → b2 → b3
begin to intersect at node c1.
Notes:
null.
Credits:
Special thanks to @stellari for adding this problem and creating all test cases.
如果没有要求此题很简单。用hashset就可以。
但是题目要求 in O(n) time and use only O(1) memory。
可以先遍历两个链表，把他们的长度变为一样长。然后逐个比较。
1 /** 2 * Definition for singly-linked list. 3 * public class ListNode { 4 * int val; 5 * ListNode next; 6 * ListNode(int x) { 7 * val = x; 8 * next = null; 9 * } 10 * } 11 */ 12 public class Solution { 13 public ListNode getIntersectionNode(ListNode headA, ListNode headB) { 14 int a=0, b = 0; 15 ListNode tempA = headA; 16 ListNode tempB = headB; 17 while (tempA != null) { 18 ++a; 19 tempA = tempA.next; 20 } 21 while (tempB != null) { 22 ++b; 23 tempB = tempB.next; 24 } 25 tempA = headA; 26 tempB = headB; 27 while (a > b) { 28 --a; 29 tempA = tempA.next; 30 } 31 while (b > a) { 32 --b; 33 tempB = tempB.next; 34 } 35 while (tempA != null) { 36 if (tempA == tempB) { 37 return tempA; 38 } else { 39 tempA = tempA.next; 40 tempB = tempB.next; 41 } 42 } 43 return null; 44 } 45 }
LeetCode Intersection of Two Linked Lists
原文：http://www.cnblogs.com/birdhack/p/4127402.html