相交链表「变题」

160. 相交链表

开头先来一个小插曲，关于「单链表」相关的总结可见 单链表的六大解题套路

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    ListNode pa = headA, pb = headB;
    while (pa != pb) {
        if (pa == null) pa = headB;
        else pa = pa.next;
        if (pb == null) pb = headA;
        else pb = pb.next;
    }
    return pa;
}

变题一：存在环的情况

思路：找到环入口，解开环，然后用和上面一样的方法找交点

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    openCycle(headA);
    openCycle(headB);
    
    ListNode pa = headA, pb = headB;
    while (pa != pb) {
        if (pa == null) pa = headB;
        else pa = pa.next;
        if (pb == null) pb = headA;
        else pb = pb.next;
    }
    return pa;
}
// 如果存在环的话，解开环
public void openCycle(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            slow = head;
            ListNode prev = null;
            while (slow != fast) {
                slow = slow.next;
                prev = fast;
                fast = fast.next;
            }
            prev.next = null;
        }
    }
}

无环的其它方法

首先将任意一条链表首尾相连，然后从另一条链表开始寻找环入口！！(曲线救国)

缺点：修改了链表的结构

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

    ListNode p = headA;
    while (p.next != null) {
        p = p.next;
    }
    p.next = headA;

    return detectCycle(headB);
}
// 找到环入口
public ListNode detectCycle(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            slow = head;
            while (slow != fast) {
                slow = slow.next;
                fast = fast.next;
            }
            return slow;
        }
    }
    return null;
}