1+ /*
2+ Author: King, wangjingui@outlook.com
3+ Date: Nov 28, 2014
4+ Problem: Intersection of Two Linked Lists
5+ Difficulty: Easy
6+ Source: https://oj.leetcode.com/problems/intersection-of-two-linked-lists/
7+
8+ Notes:
9+ Write a program to find the node at which the intersection of two singly linked lists begins.
10+ Hints:
11+ If the two linked lists have no intersection at all, return null.
12+ The linked lists must retain their original structure after the function returns.
13+ You may assume there are no cycles anywhere in the entire linked structure.
14+ Your code should preferably run in O(n) time and use only O(1) memory.
15+
16+
17+ Solution: Two iteration.
18+ */
19+ /**
20+ * Definition for singly-linked list.
21+ * public class ListNode {
22+ * int val;
23+ * ListNode next;
24+ * ListNode(int x) {
25+ * val = x;
26+ * next = null;
27+ * }
28+ * }
29+ */
30+ public class Solution {
31+ public ListNode getIntersectionNode (ListNode headA ,ListNode headB ) {
32+ ListNode cur =headA ;
33+ int lenA =0 ,lenB =0 ;
34+ while (cur !=null ) {
35+ ++lenA ;
36+ cur =cur .next ;
37+ }
38+ cur =headB ;
39+ while (cur !=null ) {
40+ ++lenB ;
41+ cur =cur .next ;
42+ }
43+ if (lenA >=lenB ) {
44+ int diff =lenA -lenB ;
45+ while (diff >0 ) {
46+ headA =headA .next ;
47+ --diff ;
48+ }
49+ while (headA !=null &&headB !=null ) {
50+ if (headA ==headB ) {
51+ return headA ;
52+ }
53+ headA =headA .next ;
54+ headB =headB .next ;
55+ }
56+ }else {
57+ int diff =lenB -lenA ;
58+ while (diff >0 ) {
59+ headB =headB .next ;
60+ --diff ;
61+ }
62+ while (headA !=null &&headB !=null ) {
63+ if (headA ==headB ) {
64+ return headA ;
65+ }
66+ headA =headA .next ;
67+ headB =headB .next ;
68+ }
69+ }
70+ return null ;
71+ }
72+ }
