每日算法 — 使用java实现链表：双指针环检测与反转操作

链表是计算机科学中最基础也最重要的线性数据结构之一。与数组不同，链表通过指针将分散在内存中的节点串联起来，支持O(1)时间复杂度的插入与删除操作。本文用Java完整实现单链表，并深入讲解三大核心算法：链表反转（迭代与递归两种范式）、Floyd判圈算法（快慢指针检测环路与定位环入口），以及快慢指针找中点与合并有序链表的组合技巧。每个算法均附带可直接运行的完整代码与复杂度分析。

链表节点定义与基础操作

首先定义链表节点ListNode，包含整型数据域val和指向下一个节点的指针next。

/**
 * 单链表节点定义
 * val 存储数据，next 指向下一个节点（尾节点为null）
 */
public class ListNode {
    int val;
    ListNode next;

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

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

为了方便测试，再提供一个工具类用于快速构建链表和打印链表内容。

/**
 * 链表工具类：构建链表与格式化输出
 */
public class LinkedListUtil {

    /**
     * 根据整数数组构建单链表，返回头节点
     */
    public static ListNode buildList(int[] arr) {
        if (arr == null || arr.length == 0) return null;
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        for (int v : arr) {
            cur.next = new ListNode(v);
            cur = cur.next;
        }
        return dummy.next;
    }

    /**
     * 将链表转换为字符串表示，如 "1 -> 2 -> 3"
     */
    public static String toString(ListNode head) {
        StringBuilder sb = new StringBuilder();
        while (head != null) {
            sb.append(head.val);
            if (head.next != null) sb.append(" -> ");
            head = head.next;
        }
        return sb.toString();
    }

    /**
     * 手动构造一个带环的链表，用于测试环检测算法
     * @param arr 链表节点值数组
     * @param pos 环入口在数组中的索引，-1表示无环
     */
    public static ListNode buildCyclicList(int[] arr, int pos) {
        if (arr == null || arr.length == 0) return null;
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        ListNode cycleEntry = null;
        for (int i = 0; i < arr.length; i++) {
            cur.next = new ListNode(arr[i]);
            cur = cur.next;
            if (i == pos) cycleEntry = cur;
        }
        if (pos >= 0) cur.next = cycleEntry;
        return dummy.next;
    }
}

核心算法一：链表反转

链表反转是面试中出现频率最高的链表题目。要求将链表中所有节点的next指针方向翻转，使原尾节点成为新头节点。

迭代法反转

迭代法使用三个指针协同工作：prev记录已反转部分的头节点，cur为当前待反转节点，nextTemp暂存cur的下一个节点以防断链。

/**
 * 迭代法反转单链表
 * 时间复杂度 O(n)，空间复杂度 O(1)
 */
public class ListReversal {

    public static ListNode reverseIterative(ListNode head) {
        ListNode prev = null;   // 已反转部分的头节点（初始为空）
        ListNode cur = head;    // 当前正在处理的节点

        while (cur != null) {
            ListNode nextTemp = cur.next; // 暂存后继，防止断链后丢失
            cur.next = prev;              // 将当前节点指向已反转部分
            prev = cur;                   // prev 前进一位
            cur = nextTemp;               // cur 前进一位
        }

        return prev; // prev 最终指向原尾节点，即新头节点
    }
}

执行流程图解（以 1 -> 2 -> 3 为例）：
1. 初始：prev=null, cur=1；暂存next=2，1.next=null，prev=1, cur=2
2. 第二步：prev=1, cur=2；暂存next=3，2.next=1，prev=2, cur=3
3. 第三步：prev=2, cur=3；暂存next=null，3.next=2，prev=3, cur=null
4. 结束，返回3，链表变为 3 -> 2 -> 1

递归法反转

递归法从链表尾部开始反转，利用函数调用栈保存节点信息，回溯时调整指针方向。

    /**
     * 递归法反转单链表
     * 时间复杂度 O(n)，空间复杂度 O(n)（递归栈深度）
     */
    public static ListNode reverseRecursive(ListNode head) {
        // 基准情况：空链表或只有一个节点，无需反转
        if (head == null || head.next == null) {
            return head;
        }

        // 递归反转后继链表，newHead 是反转后的新头节点（原尾节点）
        ListNode newHead = reverseRecursive(head.next);

        // 回溯阶段：让后继节点指向当前节点，形成反向连接
        head.next.next = head;

        // 断开当前节点原来的正向连接，防止成环
        head.next = null;

        return newHead;
    }

反转前N个节点

扩展场景：只反转链表的前N个节点，后续节点保持原序。

    /**
     * 反转链表的前 n 个节点，返回新的头节点
     * successor 记录第 n+1 个节点，用于拼接
     */
    private ListNode successor = null;

    public ListNode reverseFirstN(ListNode head, int n) {
        if (n == 1) {
            successor = head.next; // 记录第 n+1 个节点
            return head;
        }

        ListNode newHead = reverseFirstN(head.next, n - 1);
        head.next.next = head;
        head.next = successor; // 将反转后的尾节点指向后继
        return newHead;
    }

核心算法二：Floyd判圈算法

链表中的环是指某个节点的next指针指向了链表中前面的某个节点，形成闭环。检测环并定位环入口是Floyd判圈算法的经典应用。

算法原理

Floyd判圈算法使用快慢双指针：
– slow指针每次走1步，fast指针每次走2步
– 若链表无环，fast会先到达尾部（null）
– 若链表有环，fast终将追上slow（两者在环内某点相遇）

为什么一定能相遇？ 设环外长度为a，环长度为b。fast相对slow的速度为1步/单位时间，若两者都在环内，fast最多追b-1步就能与slow相遇。

环入口定位

相遇后，将其中一个指针拨回头节点，两指针改为同速（均每次1步）前进，再次相遇点即为环入口。

数学证明：设头节点到环入口距离为a，环入口到相遇点距离为b，相遇点回到环入口距离为c（b + c = 环长）。slow走了a + b，fast走了a + b + n(b + c)（n为fast在环内绕的圈数）。因为fast速度是slow的2倍：

2(a + b) = a + b + n(b + c)
=> a = (n - 1)(b + c) + c

这意味着：从头节点走a步，与从相遇点走c步再加整数圈，会到达同一位置——即环入口。

/**
 * Floyd判圈算法：检测链表是否有环，并定位环入口
 */
public class CycleDetection {

    /**
     * 检测链表是否有环
     * @return 若存在环返回相遇节点，否则返回 null
     */
    public static ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) return null;

        ListNode slow = head;
        ListNode fast = head;

        // 第一阶段：快慢指针寻找相遇点
        while (fast != null && fast.next != null) {
            slow = slow.next;       // 慢指针走1步
            fast = fast.next.next;  // 快指针走2步
            if (slow == fast) {     // 相遇，存在环
                return slow;
            }
        }

        return null; // fast 到达链表尾部，无环
    }

    /**
     * 定位环的入口节点
     * @return 环入口节点，无环返回 null
     */
    public static ListNode findCycleEntry(ListNode head) {
        ListNode meetingPoint = detectCycle(head);
        if (meetingPoint == null) return null; // 无环

        // 第二阶段：一个指针从头出发，一个从相遇点出发，同速前进
        ListNode ptr1 = head;
        ListNode ptr2 = meetingPoint;

        while (ptr1 != ptr2) {
            ptr1 = ptr1.next;
            ptr2 = ptr2.next;
        }

        return ptr1; // 再次相遇点即为环入口
    }

    /**
     * 计算环的长度
     */
    public static int cycleLength(ListNode head) {
        ListNode meetingPoint = detectCycle(head);
        if (meetingPoint == null) return 0;

        int length = 1;
        ListNode cur = meetingPoint.next;
        while (cur != meetingPoint) {
            cur = cur.next;
            length++;
        }
        return length;
    }
}

扩展：判断两个链表是否相交

若两个链表相交，则它们的尾节点必然相同。利用环检测思想，可将问题转化为判断一个链表是否有环：将链表A的尾节点指向链表B的头节点，若形成环则相交。

    /**
     * 判断两个无环链表是否相交，返回相交起始节点
     */
    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;

        ListNode pA = headA, pB = headB;

        // 双指针遍历，走完A走B，走完B走A
        // 若有交点，两指针会在交点相遇；若无交点，最终同时为null
        while (pA != pB) {
            pA = (pA == null) ? headB : pA.next;
            pB = (pB == null) ? headA : pB.next;
        }

        return pA;
    }

核心算法三：快慢指针找中点与合并有序链表

快慢指针找中点

快慢指针不仅能判圈，还能高效定位链表的中点：slow每次1步，fast每次2步，当fast到达尾部时，slow恰好位于中点。

/**
 * 快慢指针系列算法
 */
public class FastSlowPointer {

    /**
     * 查找链表的中点节点
     * 若链表长度为偶数，返回中间偏左的节点
     * 时间复杂度 O(n)，空间复杂度 O(1)
     */
    public static ListNode findMiddle(ListNode head) {
        if (head == null || head.next == null) return head;

        ListNode slow = head;
        ListNode fast = head;

        // fast 每次走2步，slow 每次走1步
        // 当 fast 到达尾部时，slow 位于中点
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        return slow;
    }

    /**
     * 查找链表的倒数第 k 个节点
     */
    public static ListNode findKthFromEnd(ListNode head, int k) {
        ListNode fast = head, slow = head;

        // fast 先走 k 步
        for (int i = 0; i < k; i++) {
            if (fast == null) return null; // k 超出链表长度
            fast = fast.next;
        }

        // fast 和 slow 同步前进，fast 到尾时 slow 即为倒数第 k 个
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }

        return slow;
    }
}

合并两个有序链表

合并两个升序链表是归并排序的底层操作，使用双指针逐一比较节点值。

/**
 * 合并两个升序链表，返回合并后的头节点
 */
public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0); // 哑节点简化边界处理
    ListNode cur = dummy;

    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) {
            cur.next = l1;
            l1 = l1.next;
        } else {
            cur.next = l2;
            l2 = l2.next;
        }
        cur = cur.next;
    }

    // 拼接剩余部分
    cur.next = (l1 != null) ? l1 : l2;

    return dummy.next;
}

综合应用：判断回文链表

回文链表要求正读反读相同。最优解法结合快慢指针找中点、链表反转和双指针比较，时间复杂度O(n)，空间复杂度O(1)。

/**
 * 判断单链表是否为回文结构
 * 策略：找中点 -> 反转后半部分 -> 双指针比较 -> 恢复链表（可选）
 */
public class PalindromeLinkedList {

    public static boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) return true;

        // 步骤1：快慢指针找中点
        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // 步骤2：反转后半部分链表
        ListNode secondHalfStart = reverseList(slow.next);

        // 步骤3：双指针比较前半部分和反转后的后半部分
        ListNode p1 = head;
        ListNode p2 = secondHalfStart;
        boolean result = true;
        while (p2 != null) {
            if (p1.val != p2.val) {
                result = false;
                break;
            }
            p1 = p1.next;
            p2 = p2.next;
        }

        // 步骤4：恢复链表（将后半部分再次反转回来）
        slow.next = reverseList(secondHalfStart);

        return result;
    }

    private static ListNode reverseList(ListNode head) {
        ListNode prev = null, cur = head;
        while (cur != null) {
            ListNode nextTemp = cur.next;
            cur.next = prev;
            prev = cur;
            cur = nextTemp;
        }
        return prev;
    }
}

完整测试与演示

/**
 * 链表算法综合测试主程序
 */
public class LinkedListDemo {

    public static void main(String[] args) {
        System.out.println("=== 链表反转测试 ===");
        ListNode list1 = LinkedListUtil.buildList(new int[]{1, 2, 3, 4, 5});
        System.out.println("原链表: " + LinkedListUtil.toString(list1));
        ListNode reversed = ListReversal.reverseIterative(list1);
        System.out.println("反转后: " + LinkedListUtil.toString(reversed));

        System.out.println("\n=== Floyd判圈算法测试 ===");
        ListNode cyclicList = LinkedListUtil.buildCyclicList(new int[]{1, 2, 3, 4, 5}, 2);
        ListNode cycleEntry = CycleDetection.findCycleEntry(cyclicList);
        if (cycleEntry != null) {
            System.out.println("环入口节点值: " + cycleEntry.val);
            System.out.println("环长度: " + CycleDetection.cycleLength(cyclicList));
        } else {
            System.out.println("无环");
        }

        ListNode noCycle = LinkedListUtil.buildList(new int[]{1, 2, 3});
        System.out.println("无环链表检测结果: " + (CycleDetection.detectCycle(noCycle) == null ? "无环" : "有环"));

        System.out.println("\n=== 快慢指针找中点测试 ===");
        ListNode list2 = LinkedListUtil.buildList(new int[]{1, 2, 3, 4, 5});
        ListNode mid = FastSlowPointer.findMiddle(list2);
        System.out.println("链表 1->2->3->4->5 的中点: " + mid.val);

        ListNode list3 = LinkedListUtil.buildList(new int[]{1, 2, 3, 4, 5, 6});
        ListNode mid2 = FastSlowPointer.findMiddle(list3);
        System.out.println("链表 1->2->3->4->5->6 的中点(偏左): " + mid2.val);

        System.out.println("\n=== 倒数第 k 个节点测试 ===");
        ListNode list4 = LinkedListUtil.buildList(new int[]{10, 20, 30, 40, 50});
        ListNode kth = FastSlowPointer.findKthFromEnd(list4, 2);
        System.out.println("倒数第2个节点: " + (kth != null ? kth.val : "null"));

        System.out.println("\n=== 合并有序链表测试 ===");
        ListNode l1 = LinkedListUtil.buildList(new int[]{1, 3, 5});
        ListNode l2 = LinkedListUtil.buildList(new int[]{2, 4, 6});
        ListNode merged = FastSlowPointer.mergeTwoLists(l1, l2);
        System.out.println("合并 1->3->5 和 2->4->6: " + LinkedListUtil.toString(merged));

        System.out.println("\n=== 回文链表测试 ===");
        ListNode palindrome = LinkedListUtil.buildList(new int[]{1, 2, 3, 2, 1});
        System.out.println("1->2->3->2->1 是回文: " + PalindromeLinkedList.isPalindrome(palindrome));

        ListNode notPalindrome = LinkedListUtil.buildList(new int[]{1, 2, 3, 4, 5});
        System.out.println("1->2->3->4->5 是回文: " + PalindromeLinkedList.isPalindrome(notPalindrome));
    }
}

预期输出：

=== 链表反转测试 ===
原链表: 1 -> 2 -> 3 -> 4 -> 5
反转后: 5 -> 4 -> 3 -> 2 -> 1

=== Floyd判圈算法测试 ===
环入口节点值: 3
环长度: 3
无环链表检测结果: 无环

=== 快慢指针找中点测试 ===
链表 1->2->3->4->5 的中点: 3
链表 1->2->3->4->5->6 的中点(偏左): 3

=== 倒数第 k 个节点测试 ===
倒数第2个节点: 40

=== 合并有序链表测试 ===
合并 1->3->5 和 2->4->6: 1 -> 2 -> 3 -> 4 -> 5 -> 6

=== 回文链表测试 ===
1->2->3->2->1 是回文: true
1->2->3->4->5 是回文: false

复杂度总结

总结

本文围绕单链表展开，系统实现了三大核心算法族：

• 链表反转：迭代法空间最优，递归法代码最简洁。前N个节点反转是更通用的扩展模式。
• Floyd判圈算法：快慢指针的经典应用，不仅能检测环，还能通过数学推导精确定位环入口并计算环长。其思想可延伸至判断两链表相交等问题。
• 快慢指针与合并：找中点、找倒数第k个、合并有序链表均是双指针技巧的变体。将这些子算法组合，即可在O(n)时间、O(1)空间内解决回文链表等复杂问题。

链表的精髓在于指针的重新布线。掌握上述算法后，读者可继续挑战更复杂的问题：重排链表（L0→Ln→L1→Ln-1…）、复制带随机指针的链表、K个一组反转链表等。