[LeetCode]--160. 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.
Credits:
Special thanks to @stellari for adding this problem and creating all test cases.

因为受上面一个问题影响Java单链表逆转所以我想着先逆转后求后面的子串，其实想多了，只要有一个公共的就当时后面的全部是公共。

解法一:
第一遍循环，找出两个链表的长度差N
第二遍循环，长链表先走N步，然后同时移动，判断是否有相同节点
解法一就相对简单粗暴，容易理解。

/** 
 * 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) {  
        if(headA==null || headB==null) return null;  

        ListNode p = headA;  
        ListNode q = headB;  
        int pcount = 0;  
        int qcount = 0;  
        while(p.next != null || q.next != null) {  
            if(p == q) return p;  
            if(p.next != null) p = p.next; else ++qcount;  
            if(q.next != null) q = q.next; else ++pcount;  
        }  
        if(p != q) return null;  
        p = headA;  
        q = headB;  
        while(pcount-- != 0) {  
            p = p.next;  
        }  

        while(qcount-- != 0) {  
            q = q.next;  
        }  

        while(p != q) {  
            p = p.next;  
            q = q.next;  
        }  
        return p;  
    }  
}  

解法二:
链表到尾部后,跳到另一个链表的头部, 另外一个链表的引用移到最后，此时跳过来的引用所在点就为第二个链表的开始点，然后再次一起遍历，相遇即为intersection points.

/** 
 * 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) {  
        if(headA==null || headB==null) return null;  

        ListNode p = headA;  
        ListNode q = headB;  
        if(p == q) return p;          
        while(p!=null && q!=null) {  
            p = p.next;  
            q = q.next;  
        }  

        if(p==null) p = headB; else q = headA;  

        while(p!=null && q!=null) {  
            p = p.next;  
            q = q.next;  
        }  

        if(p==null) p = headB; else q = headA;  

        while(p!=null && q!=null) {  
            if(p==q) return p;  
            p = p.next;  
            q = q.next;  
        }  
        return null;  
    }  
}  

就是先一起移动，如果一个到头了，就指向另一个的头，另一个到尾了，就说明这个指向的就是下次一起开始的地方。

解法三：
用两个引用，一个快一个慢，快的每次移动两个节点，当。。。。。。。。。。。我以为我理解了，其实没理解，然后去打断点调试就发现出问题了，不过leetcode上面显示Accept！很奇怪，先贴个代码，等以后问问别人。

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        // get the tail of list A.
        ListNode node = headA;
        while (node.next != null) {
            node = node.next;
        }
        node.next = headB;
        ListNode result = listCycleII(headA);
        node.next = null;
        return result;
    }

    private ListNode listCycleII(ListNode head) {
        ListNode slow = head, fast = head.next;

        while (slow != fast) {
            if (fast == null || fast.next == null) {
                return null;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        slow = head;
        fast = fast.next;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }