leetcode160

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.

/**
 * Created by hadoop on 17-10-2.
 */
public class 两个链表的相交节点 {
    /*该方法十分巧妙，如果两个链表的长度相等，依次比较每个节点是否相等即可。一般的做法是将两个链表的长度设置相等即可。这里利用
    两次循环和两个指针，第一次将不同的元素略过，第二次如果有相交的元素则返回相交的节点，如果没有，就返回null。如果短的链表已经循环完毕
    就将指针指向不同的链表的头结点。
     */
    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
       if (headA==null || headB == null)
           return null;
        ListNode curA = headA;
        ListNode curB = headB;

        while (curA != curB){
            curA = curA == null ? headB : curA.next;
            curB = curB == null ? headA : curB.next;
        }

        return curA;

    }

    public static void main(String[] args){
        ListNode head = new ListNode(0);
        ListNode head1 = new ListNode(1);
        ListNode node = new ListNode(2);
        ListNode node2 = new ListNode(3);


        head.next = node;
        head1.next = node;
        node.next = node2;

        ListNode result = getIntersectionNode(head,head1);
        System.out.print(result.val);
    }
}