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:

• 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
• 从后对齐，只需比较后面的元素，有没有相同的
• 没有中间有一个相同的，后面又不同的情况

• /** * 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) {        ListNode result = null;		ListNode tempa=headA;		ListNode tempb=headB;		if (headA == null || headB == null) {			return null;		}		int a = 1, b = 1;		while (headA.next != null) {			a++;			headA = headA.next;		}		while (headB.next != null) {			b++;			headB = headB.next;		}		int temp = 0;		if (a >= b) {			temp = a - b;			while (temp != 0) {				tempa = tempa.next;				temp--;			}		} else {			temp = b - a;			while (temp != 0) {				tempb = tempb.next;				temp--;			}		}		while (tempa!= null) {			if (tempa == tempb) {				result = tempa;				break;			} else {				tempa = tempa.next;				tempb = tempb.next;			}		}		return result;    }}

  　　

leetcode Intersection of Two Linked Lists