18. 链表的中间节点：找到链表的中间节点。

要找到链表的中间节点，可以使用快慢指针（Two Pointers）的方法。这种方法非常高效，时间复杂度为 O(n)，空间复杂度为 O(1)。

1. 问题描述

给定一个单链表，要求找到链表的中间节点。如果链表的节点数是奇数，那么返回唯一的中间节点；如果节点数是偶数，则返回两个中间节点中的第二个。

2. 算法思路

使用两个指针：

• 慢指针 slow：每次移动一步。
• 快指针 fast：每次移动两步。

当 fast 指针到达链表的末尾时，slow 指针正好到达链表的中间节点。这样，slow 指针指向的节点就是链表的中间节点。

3. 代码实现

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}

public class MiddleOfLinkedList {

    public ListNode findMiddleNode(ListNode head) {
        if (head == null) {
            return null;
        }

        ListNode slow = head;
        ListNode fast = head;

        // 移动快慢指针
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // 当 fast 指针到达链表末尾时，slow 指针在中间节点
        return slow;
    }

    public static void main(String[] args) {
        MiddleOfLinkedList solution = new MiddleOfLinkedList();

        // 构造一个链表：1 -> 2 -> 3 -> 4 -> 5
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);

        ListNode middleNode = solution.findMiddleNode(head);
        System.out.println("Middle node value: " + middleNode.val);
    }
}

4. 示例解释

假设链表为 1 -> 2 -> 3 -> 4 -> 5：

1. 初始状态下：
   • slow 指向节点 1
   • fast 指向节点 1
2. 第一次迭代后：
   • slow 指向节点 2
   • fast 指向节点 3
3. 第二次迭代后：
   • slow 指向节点 3
   • fast 指向节点 5
4. 第三次迭代时，fast.next 为空，循环结束，此时 slow 指向节点 3，即链表的中间节点。

5. 复杂度分析

• 时间复杂度：O(n)，其中 n 是链表中的节点数。遍历整个链表一次就可以找到中间节点。
• 空间复杂度：O(1)，只使用了两个指针来遍历链表，没有使用额外的空间。

6. 总结

使用快慢指针法，可以高效地找到链表的中间节点。这种方法简单且实用，尤其适合处理大规模链表的情况。通过每次移动不同步数的两个指针，可以在一次遍历中找到链表的中间节点。