Intersection of Two Linked Lists

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.

给定两个链表，判断它们是否交叉，如果没有交叉返回空，如果有交叉，返回交叉的起始点。我们遍历两个链表，判断元素是否相等，但是前提是两个链表长度相同。题目中的两个链表长度不同，我们可以同时遍历两个链表A,B，当A链表为空时让它指向B链表的头结点，当B链表为空时，让B链表指向A链表的头结点（这种情况是A链表比B链表短），同理A链表比B链表长的情况。代码如下：

/**
 * 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 curA = headA;
        ListNode curB = headB;
        while(curA != curB) {
            curA = (curA == null) ? headB : curA.next;
            curB = (curB == null) ? headA : curB.next;
        }
        return curA;
    }
}