LeetCode 876. 链表的中间结点

Categories:

题目描述
思路分析
1. 解法一：快慢指针（推荐）
相似题目

题目描述

✅ 876. 链表的中间结点

思路分析

解法一：快慢指针（推荐）

核心思路：

使用快慢指针，快指针每次走两步，慢指针每次走一步。

当快指针到达末尾时，慢指针正好位于中间节点。

复杂度分析：

时间复杂度：O(n)，其中 n 表示链表节点数。

空间复杂度：O(1)，仅使用常数额外指针。

// 快慢指针找中点
class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        return slow;
    }
}

// 快慢指针找中点
func middleNode(head *ListNode) *ListNode {
	slow, fast := head, head
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}
	return slow
}

相似题目

题目	难度	考察点
141. 环形链表	简单	快慢指针
142. 环形链表 II	中等	快慢指针
143. 重排链表	中等	快慢指针
234. 回文链表	简单	快慢指针
2095. 删除链表的中间节点	中等	快慢指针
19. 删除链表的倒数第 N 个结点	中等	快慢指针

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/67928740