Intersection of Two Linked Lists

问题来源：https://leetcode.com/problems/intersection-of-two-linked-lists/

/**
 * 
 * <p>
 * ClassName IntersectionOfTwoLinkedLists
 * </p>
 * <p>
 * Description 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.
 * </p>
 * 
 * @author TKPad wangx89@126.com
 *         <p>
 *         Date 2015年3月26日 下午1:30:20
 *         </p>
 * @version V1.0.0
 *
 */
class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}

public class IntersectionOfTwoLinkedLists {
    ListNode temp;
    // Last executed input: Intersected at ‘60‘:
    // {1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,41,43,45,47,49,51,53,55,57,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94},
    // {2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40,42,44,46,48,50,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94}
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA != null && headB != null) {
            if (headA.val < headB.val) {
                while (headA.val < headB.val) {
                    if (headA.next != null) {
                        headA = headA.next;
                    } else {
                        break;
                    }
                }
                if (headA.val != headB.val) {
                    temp = getIntersectionNode(headA, headB.next);
                } else {
                    temp = headA;
                }
            } else if (headA.val > headB.val) {
                while (headB.val < headA.val) {
                    if (headB.next != null) {
                        headB = headB.next;
                    } else {
                        break;
                    }
                }
                if (headA.val != headB.val) {
                    temp = getIntersectionNode(headA.next, headB);
                } else {
                    temp = headA;
                }
            } else {
                temp = headA;
            }
        }
        return temp;
    }

    public static void main(String[] args) {
        // Runtime Error Message: Line 38: java.lang.StackOverflowError
        // Last executed input: No intersection: {1,3,5,7,9,11,13,15,17,19,21}, {2}

        // Last executed input: No intersection: {1}, {2,4,6,8,10,12,14,16,18,20,22}

        ListNode l1 = new ListNode(18);
        // ListNode l11 = new ListNode(10);
        // l1.next = l11;

        ListNode l2 = new ListNode(1);
        ListNode l3 = new ListNode(4);
        ListNode l4 = new ListNode(6);
        ListNode l5 = new ListNode(8);
        ListNode l6 = new ListNode(10);
        ListNode l7 = new ListNode(12);
        ListNode l8 = new ListNode(14);
        ListNode l9 = new ListNode(16);
        ListNode l10 = new ListNode(18);
        l2.next = l3;
        l3.next = l4;
        l4.next = l5;
        l5.next = l6;
        l6.next = l7;
        l7.next = l8;
        l8.next = l9;
        l9.next = l10;
        ListNode intersectionNode = new IntersectionOfTwoLinkedLists().getIntersectionNode(l1, l2);
        if (intersectionNode != null)
            System.out.println(intersectionNode.val);
        else
            System.out.println("null");
    }
}