LeeCode-链表

参考Leecode

环形链表

分析：
方式一：双指针法，我们可以用两个指针，一个快指针一次走两步，一个慢指针，一次走一步，若走到尾结点（next=null）那么表示无环，若快指针再次与慢指针相遇则存在环。
方式二：hash表，我们遍历所有结点并在map中存储每个结点的引用（或内存地址）。如果当前结点为空结点 nullptr（即已检测到链表尾部的下一个结点），那么我们已经遍历完整个链表，并且该链表不是环形链表。如果当前结点的引用已经存在于map中，那么返回 true（即该链表为环形链表）。

public class 双指针 {
    public static void main(String[] args) {
        Node tail = new Node(1, null);
        Node n1 = new Node(2, tail);
        Node n2 = new Node(3, n1);
        Node n3 = new Node(4, n2);
        Node n4 = new Node(5, n3);
        Node n5 = new Node(6, n4);
        Node head = new Node(7, n5);
        tail.next = n4;
        System.out.println(hasCyc(head));
    }
    public static boolean hasCyc(Node head) {
        Node slowPtr = head;
        Node quickPtr = head;
        do {
            // 无环
            if (quickPtr == null || quickPtr.next == null) {
                return false;
            }
            // 移动指针
            slowPtr = slowPtr.next;
            quickPtr = quickPtr.next.next;
        } while (slowPtr != quickPtr);
        return true;
    }
    static class Node {
        int data;
        Node next;
        public Node(int data, Node next) {
            this.data = data;
            this.next = next;
        }
    }
}

public class HashDemo {
    public static void main(String[] args) {
        Node tail = new Node(1, null);
        Node n1 = new Node(2, tail);
        Node n2 = new Node(3, n1);
        Node n3 = new Node(4, n2);
        Node n4 = new Node(5, n3);
        Node n5 = new Node(6, n4);
        Node head = new Node(7, n5);
        tail.next = n4;
        System.out.println(hasCyc_hash(head));
    }
    public static boolean hasCyc_hash(Node head) {
        HashSet<Node> sets = new HashSet<>();
        Node ptr = head;
        // 遍历
        while (ptr != null) {
            // 已经存在表示有环
            if (sets.contains(ptr)) {
                return true;
            }
            // 不存在，添加到集合中
            sets.add(ptr);
            ptr = ptr.next;
        }
        return false;
    }
    static class Node {
        int data;
        Node next;
        public Node(int data, Node next) {
            this.data = data;
            this.next = next;
        }
    }
}

环形链表二

分析：

public class EntranceDemo {
    public static void main(String[] args) {
        Node tail = new Node(1, null);
        Node n2 = new Node(2, tail);
        Node n3 = new Node(3, n2);
        Node n4 = new Node(4, n3);
        Node n5 = new Node(5, n4);
        Node n6 = new Node(6, n5);
        Node head = new Node(7, n6);
        // 入口点测试
        tail.next = n5;
        System.out.println(cycEntrance(head));
    }
    public static int cycEntrance(Node head) {
        Node slowPtr = head;
        Node quickPtr = head;
        do {
            // 无环
            if (quickPtr == null || quickPtr.next == null) {
                return -1;
            }
            // 移动指针
            slowPtr = slowPtr.next;
            quickPtr = quickPtr.next.next;
        } while (slowPtr != quickPtr);
        // 有环，找入口点,将慢指针重新从head开始一次走一步，快指针从相遇的位置开始一次走一步，直到下次相遇
        slowPtr = head;
        while (slowPtr != quickPtr) {
            slowPtr = slowPtr.next;
            quickPtr = quickPtr.next;
        }
        return slowPtr.data;
    }
    static class Node {
        int data;
        Node next;
        public Node(int data, Node next) {
            this.data = data;
            this.next = next;
        }
    }
}

输出：5

相交链表

删除链表的倒数第N个节点

反转链表