相交链表

LeetCode 160. 相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
题目数据 保证 整个链式结构中不存在环。 注意，函数返回结果后，链表必须 保持其原始结构 。

import java.util.HashSet;
import java.util.Set;

public class IntersectionOfTwoLinkedLists {

    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    /**
     * 执行结果：通过
     * 执行用时：5 ms, 在所有 Java 提交中击败了24.05%的用户
     * 内存消耗：43.7 MB, 在所有 Java 提交中击败了93.68%的用户
     * 通过测试用例：39 / 39
     *
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Set<ListNode> set = new HashSet<ListNode>();
        while (headA != null) {
            set.add(headA);
            headA = headA.next;
        }
        while (headB != null) {
            if (set.contains(headB)) {
                return headB;
            }
            headB = headB.next;
        }
        return null;
    }

    /**
     * 执行结果：通过
     * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
     * 内存消耗：44.5 MB, 在所有 Java 提交中击败了20.15%的用户
     * 通过测试用例：39 / 39
     *
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode1(ListNode headA, ListNode headB) {
        ListNode ACycleNode = detectCycle(headA);
        ListNode BCycleNode = detectCycle(headB);
        if (ACycleNode == null & BCycleNode == null) {
            ListNode curtA = headA;
            ListNode curtB = headB;
            int countA = 1;
            int countB = 1;
            while (curtA.next != null) {
                curtA = curtA.next;
                countA++;
            }
            while (curtB.next != null) {
                curtB = curtB.next;
                countB++;
            }
            if (curtA != curtB) {
                return null;
            }
            curtA = headA;
            curtB = headB;
            if (countA >= countB) {
                for (int i = 0; i < countA - countB; i++) {
                    curtA = curtA.next;
                }
            } else {
                for (int i = 0; i < countB - countA; i++) {
                    curtB = curtB.next;
                }
            }
            while (curtA != curtB) {
                curtA = curtA.next;
                curtB = curtB.next;
            }
            return curtA;
        } else if ((ACycleNode == null & BCycleNode != null) || (ACycleNode != null & BCycleNode == null)) {
            return null;
        } else if (ACycleNode != null & BCycleNode != null) {
            if (ACycleNode == BCycleNode) {
                ListNode curtA = headA;
                ListNode curtB = headB;
                int countA = 1;
                int countB = 1;
                while (curtA != ACycleNode) {
                    curtA = curtA.next;
                    countA++;
                }
                while (curtB != BCycleNode) {
                    curtB = curtB.next;
                    countB++;
                }
                curtA = headA;
                curtB = headB;
                if (countA >= countB) {
                    for (int i = 0; i < countA - countB; i++) {
                        curtA = curtA.next;
                    }
                }else {
                    for (int i = 0; i < countB - countA; i++) {
                        curtB = curtB.next;
                    }
                }
                while (curtA != curtB){
                    curtA = curtA.next;
                    curtB = curtB.next;
                }
                return curtA;
            }else {
                while (ACycleNode == BCycleNode||ACycleNode == ACycleNode){
                    ACycleNode = ACycleNode.next;
                }
                if(ACycleNode == BCycleNode){
                    return ACycleNode;
                }else {
                    return null;
                }
            }
        }
        return null;
    }

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