LeetCode刷题Day05——链表（链表元素删除、相交、环形链表）

/**
 * <pre>
 * 最简单的方法显然是先遍历一遍链表，知道长度后重新遍历一次就可以找到指定节点了，由此方法我们不难延伸到另一种解法
 * 既然是删除倒数第n个节点，那么也就是一旦遇到最后一个节点那么它前面的第n个节点就是要删除的节点
 * 我们只要使用快慢指针，慢指针在快指针前n位，那么当快指针到达链表尾时慢指针所指的就是需要删除的节点
 * </pre>
 *
 * @author <a href="https://github.com/kil1ua">Ken-Chy129</a>
 * @date 2023/1/5 14:52
 */
public class 删除链表的倒数第N个结点19 {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode pos1=new ListNode(), pos2=head, res = pos1;
        pos1.next = head;
        int i=0;
        while (pos2 != null) {
            if (i < n) { // 找的是链尾的前第n+1个，这样才能删除链尾的第n个
                i++;
            } else {
                pos1 = pos1.next;
            }
            pos2 = pos2.next;
        }
        pos1.next = pos1.next.next;
        return res.next;
    }
    public ListNode removeNthFromEnd2(ListNode head, int n) {
        ListNode p = new ListNode(), res = p;
        p.next = head;
        Deque<ListNode> stack = new LinkedList<>();
        while (p != null) {
            stack.push(p);
            p = p.next;
        }
        for (int i=0; i<n; i++) {
            stack.pop();
        }
        p = stack.peek();
        p.next = p.next.next;
        return res.next;
    }
}

/**
 * <pre>
 * 计算出两个链表的长度，让长的链表先移动到和短的链表一样长（因为交点不可能在前面部分），随后两个链表同时移动，相等时即为交点
 * 或者使用哈希表将第一个链表的元素进行存储，然后遍历第二个链表判断当前节点是否存在在哈希表中
 * 两者时间复杂度相同，但是哈希表需要额外的空间开销（哈希表查找元素是需要O(1)的时间复杂度，所以总的时间开销相同）
 * </pre>
 *
 * @author <a href="https://github.com/kil1ua">Ken-Chy129</a>
 * @date 2023/1/6 13:49
 */
public class 链表相交160 {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode pa = headA, pb = headB;
        int lena=1, lenb=1;
        while (pa != null) {
            pa = pa.next;
            lena++;
        }
        while (pb != null) {
            pb = pb.next;
            lenb++;
        }
        pa = headA;
        pb = headB;
        if (lena > lenb) {
            for (int i=1; i<=lena-lenb; i++) {
                pa = pa.next;
            }
        } else if (lena < lenb) {
            for (int i = 1; i <= lenb - lena; i++) {
                pb = pb.next;
            }
        }
        while (pa != null) {
            if (pa == pb) {
                return pa;
            }
            pa = pa.next;
            pb = pb.next;
        }
        return null;
    }
    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        Set<ListNode> visited = new HashSet<ListNode>();
        ListNode temp = headA;
        while (temp != null) {
            visited.add(temp);
            temp = temp.next;
        }
        temp = headB;
        while (temp != null) {
            if (visited.contains(temp)) {
                return temp;
            }
            temp = temp.next;
        }
        return null;
    }
}

/**
 * <pre>
 * 可以使用快慢指针的方式，让快指针每次走两格，慢指针每次走一格，快指针先入环而且一定会在环中与慢指针相遇
 * 因为在环中对于慢指针来说，其实快指针是以每次1的速度向他逼近，最终一定会碰上
 * </pre>
 *
 * @author <a href="https://github.com/kil1ua">Ken-Chy129</a>
 * @date 2023/1/6 14:26
 */
public class 环形链表II142 {
    public ListNode detectCycle(ListNode head) {
        ListNode pos1 = head, pos2 = head;
        while (pos2 != null) {
            if (pos2.next == null) {
                return null;
            }
            pos1 = pos1.next;
            pos2 = pos2.next.next;
            if (pos2 == pos1) {
                ListNode p = head;
                while (p != pos1) {
                    p = p.next;
                    pos1 = pos1.next;
                }
                return p;
            }
        }
        return null;
    }
}