每日算法 — 使用java实现链表：反转操作与Floyd判圈算法

链表（Linked List）是计算机科学中最基础也最灵活的数据结构之一。与数组不同，链表通过指针动态连接节点，无需预先分配连续内存，在插入和删除操作上具有 O(1) 的时间优势。本文将从零实现一个完整的单链表，重点讲解反转链表的经典迭代解法，以及 Floyd 判圈算法——一个用于检测链表中环的数学 elegant 算法。

数据结构定义

链表由一系列节点组成，每个节点包含数据域和指针域。单链表的指针仅指向下一个节点，形成线性结构。

Java 实现

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

/**
 * 单链表完整实现，包含基础操作、反转与环检测
 */
public class LinkedList {

    /**
     * 链表节点定义
     */
    static class Node {
        int val;
        Node next;

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

    private Node head; // 链表头节点
    private int size;  // 链表长度

    /**
     * 在链表尾部添加元素
     *
     * @param val 待添加的值
     */
    public void add(int val) {
        Node newNode = new Node(val);
        if (head == null) {
            head = newNode;
        } else {
            Node cur = head;
            while (cur.next != null) {
                cur = cur.next;
            }
            cur.next = newNode;
        }
        size++;
    }

    /**
     * 迭代反转链表：三指针法
     * prev -> cur -> next 逐步反转指针方向
     *
     * 时间复杂度 O(n)，空间复杂度 O(1)
     */
    public void reverse() {
        Node prev = null;
        Node cur = head;
        while (cur != null) {
            Node next = cur.next; // 暂存下一个节点
            cur.next = prev;      // 反转当前指针
            prev = cur;           // prev 前进一步
            cur = next;           // cur 前进一步
        }
        head = prev; // 新的头节点
    }

    /**
     * 递归反转链表
     *
     * @param node 当前处理的节点
     * @return 反转后的新头节点
     */
    public Node reverseRecursive(Node node) {
        if (node == null || node.next == null) {
            return node; // 递归终止条件
        }
        Node newHead = reverseRecursive(node.next);
        node.next.next = node; // 将下一个节点指向当前节点
        node.next = null;      // 断开原指针，防止环
        return newHead;
    }

    /**
     * Floyd 判圈算法（龟兔赛跑算法）
     * 使用快慢指针检测链表中是否存在环
     *
     * 原理：若存在环，快指针终将追上慢指针；若无环，快指针先到达末尾
     *
     * @return true 若存在环
     */
    public boolean hasCycle() {
        if (head == null || head.next == null) {
            return false;
        }
        Node slow = head; // 慢指针，每次走一步
        Node fast = head; // 快指针，每次走两步

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                return true; // 两指针相遇，存在环
            }
        }
        return false; // 快指针到达末尾，无环
    }

    /**
     * 若存在环，返回环的入口节点
     * 数学证明：设头到入口距离为 a，环长为 b，相遇时慢指针走了 a + mb + x，
     * 快指针走了 a + nb + x。由于快指针速度是慢指针两倍，可得从头和相遇点同步走
     * 必在入口相遇
     *
     * @return 环入口节点，若无环返回 null
     */
    public Node detectCycleEntry() {
        if (head == null || head.next == null) {
            return null;
        }
        Node slow = head;
        Node fast = head;

        // 第一阶段：寻找相遇点
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                break; // 找到相遇点
            }
        }

        // 无环情况
        if (fast == null || fast.next == null) {
            return null;
        }

        // 第二阶段：寻找入口
        Node ptr = head;
        while (ptr != slow) {
            ptr = ptr.next;
            slow = slow.next;
        }
        return ptr; // 入口节点
    }

    /**
     * 哈希表法检测环（辅助理解，非最优）
     * 时间 O(n)，空间 O(n)
     */
    public boolean hasCycleByHash() {
        Set<Node> visited = new HashSet<>();
        Node cur = head;
        while (cur != null) {
            if (visited.contains(cur)) {
                return true;
            }
            visited.add(cur);
            cur = cur.next;
        }
        return false;
    }

    /**
     * 打印链表内容
     */
    public void printList() {
        Node cur = head;
        while (cur != null) {
            System.out.print(cur.val + " -> ");
            cur = cur.next;
        }
        System.out.println("null");
    }

    public Node getHead() {
        return head;
    }

    public void setHead(Node head) {
        this.head = head;
    }

    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);

        System.out.print("原始链表: ");
        list.printList();

        // 反转测试
        list.reverse();
        System.out.print("反转后: ");
        list.printList();

        // 环检测测试：构造一个有环链表 1 -> 2 -> 3 -> 4 -> 2
        Node n1 = new Node(1);
        Node n2 = new Node(2);
        Node n3 = new Node(3);
        Node n4 = new Node(4);
        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n2; // 形成环

        LinkedList cycleList = new LinkedList();
        cycleList.setHead(n1);
        System.out.println("有环链表检测结果: " + cycleList.hasCycle());
        Node entry = cycleList.detectCycleEntry();
        System.out.println("环入口节点值: " + (entry != null ? entry.val : "无环"));
    }
}

复杂度分析

Floyd 判圈算法的精妙之处在于它仅使用两个指针就解决了环检测问题，空间复杂度为 O(1)，远优于哈希表法的 O(n)。

总结

链表是许多高级数据结构和算法的基础。掌握链表的反转技巧（三指针法）和环检测（Floyd 算法），不仅能应对面试高频题，更能深入理解指针操作和数学推理在算法设计中的力量。