LintCode 题解｜228. 入门题：链表的中点
最新回答
避而不谈
2026-01-01 16:37:21
答案：使用快慢指针法可以高效地找到链表的中点，时间复杂度为O(n/2)。
方法思路：
- 初始化指针：设置两个指针slow和fast，初始时都指向链表头节点。
- 移动指针：快指针fast每次移动两步，慢指针slow每次移动一步。
- 终止条件：当快指针fast到达链表末尾（即fast为null或fast.next为null）时，慢指针slow所在的位置即为链表的中点。
- 处理偶数长度：如果链表长度为偶数，慢指针slow会指向中间偏左的节点，符合题目要求。
解决代码：
/ * Definition for ListNode * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */public class Solution { / * @param head: the head of linked list. * @return: a middle node of the linked list */ public ListNode middleNode(ListNode head) { if (head == null || head.next == null) { return head; } ListNode slow = head, fast = head.next; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } return slow; }}代码解释：
- 初始化检查：如果链表为空或只有一个节点，直接返回头节点。
- 指针初始化：slow指向头节点，fast指向头节点的下一个节点，确保在偶数长度时返回中间偏左的节点。
- 循环移动指针：fast每次移动两步，slow每次移动一步，直到fast无法继续移动（到达链表末尾）。
- 返回结果：此时slow指向链表的中点，返回slow。
这种方法确保了在O(n/2)的时间复杂度内找到中点，且只需遍历链表一次，高效且简洁。
热门标签
