题目：
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 → b3begin to intersect at node c1.
Notes:
If the two linked lists have no intersection at all, return null.The linked lists must retain their original structure after the function returns.You may assume there are no cycles anywhere in the entire linked structure.Your code should preferably run in O(n) time and use only O(1) memory.
思路 方法超屌！！！
1. 得到2个链条的长度。
2. 将长的链条向前移动差值（len1 - len2）
3. 两个指针一起前进，遇到相同的即是交点，如果没找到，返回null.
相当直观的解法。空间复杂度O(1)， 时间复杂度O(m+n)
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 if (headA == null || headB == null) { 15 return null; 16 } 17 18 ListNode cur = headA; 19 int len1 = getLen(headA); 20 int len2 = getLen(headB); 21 22 int cnt = Math.abs(len1 - len2); 23 24 // cut the longer list. 25 if (len1 > len2) { 26 while (cnt > 0) { 27 headA = headA.next; 28 cnt--; 29 } 30 } else { 31 while (cnt > 0) { 32 headB = headB.next; 33 cnt--; 34 } 35 } 36 37 while (headA != null) { 38 if (headA == headB) { 39 return headA; 40 } 41 42 headA = headA.next; 43 headB = headB.next; 44 } 45 46 return null; 47 } 48 49 public int getLen(ListNode head) { 50 int cnt = 0; 51 while (head != null) { 52 head = head.next; 53 cnt++; 54 } 55 56 return cnt; 57 } 58 }
reference： http://www.cnblogs.com/yuzhangcmu/p/4128794.html
转载于:https://www.cnblogs.com/hygeia/p/4759571.html
