链表基础题

倒数第 k 个节点

双指针：先走 k-1 步，再同步走到尾。

public static Integer lastK(Node head, int k) {
    if (k <= 0 || head == null) {
        return null;
    }
    Node p = head;
    while (--k > 0) {
        if (p == null) {
            return null;
        }
        p = p.next;
    }
    if (p == null) {
        return null;
    }
    Node p2 = head;
    while (p.next != null) {
        p = p.next;
        p2 = p2.next;
    }
    return p2.data;
}

是否有环

快慢指针。

public static boolean hasCycle(Node head) {
    Node slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            return true;
        }
    }
    return false;
}

两个无环单链表是否相交

走到各自尾节点，尾相同则相交（Y 形）。

public static boolean intersect(Node headA, Node headB) {
    if (headA == null || headB == null) {
        return false;
    }
    while (headA.next != null) {
        headA = headA.next;
    }
    while (headB.next != null) {
        headB = headB.next;
    }
    return headA == headB;
}