How do I solve the 'Middle of the Linked List' problem?

The best approach is the two-pointer technique: one pointer moves two steps at a time, and the other moves one step. The slower pointer reaches the middle when the fast one reaches the end.

What if the list has an even number of nodes?

If the list has two middle nodes, you must return the second one. For example, with the list [1, 2, 3, 4], return 3.

What is the time complexity of the two-pointer solution?

The time complexity is O(n), where n is the number of nodes in the linked list, since we traverse the list once.

Are there any edge cases to consider for this problem?

Yes, the list could have one node, which is trivially the middle. Also, an even-length list should return the second middle node.

How does the two-pointer technique work?

The two-pointer technique uses two pointers: one moves two steps at a time, and the other moves one step at a time. When the fast pointer reaches the end, the slow pointer will be at the middle.

#876

Easy

auto_awesome链表指针操作

LeetCode 题解工作台

链表的中间结点

给你单链表的头结点 head ，请你找出并返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。示例 1：输入： head = [1,2,3,4,5] 输出： [3,4,5] 解释：链表只有一个中间结点，值为 3 。示例 2：输入： head = [1,2,3,4,5,6] 输出…

链表双指针

题目描述

给你单链表的头结点 head ，请你找出并返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

示例 1：

输入：head = [1,2,3,4,5]
输出：[3,4,5]
解释：链表只有一个中间结点，值为 3 。

示例 2：

输入：head = [1,2,3,4,5,6]
输出：[4,5,6]
解释：该链表有两个中间结点，值分别为 3 和 4 ，返回第二个结点。

提示：

链表的结点数范围是 [1, 100]
1 <= Node.val <= 100

lightbulb

解题思路

方法一：快慢指针

我们定义快慢指针 $\textit{fast}$ 和 $\textit{slow}$ ，初始时均指向链表的头结点。

快指针 $\textit{fast}$ 每次走两步，慢指针 $\textit{slow}$ 每次走一步。当快指针走到链表的尾部时，慢指针所指的结点即为中间结点。

时间复杂度 $O(n)$ ，其中 $n$ 是链表的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        slow = fast = head
        while fast and fast.next:
            slow, fast = slow.next, fast.next.next
        return slow

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Ensure the candidate can explain the two-pointer technique and its efficiency.
question_mark
Look for a solid understanding of edge cases like a list with a single node or an even-length list.
question_mark
Evaluate if the candidate can discuss how pointer manipulation works in the context of linked lists.

warning

常见陷阱

外企场景

error
Incorrectly handling even-length lists by returning the first middle node instead of the second.
error
Failing to properly set up the two-pointer technique, leading to incorrect traversal of the list.
error
Not addressing edge cases, like lists with only one node.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Finding the middle node using an iterative approach instead of two pointers.
arrow_right_alt
Using a recursive approach to find the middle node in the list.
arrow_right_alt
Returning the middle node's value instead of the node itself.

help

常见问题

外企场景

继续练习

#234 回文链表 #160 相交链表 #148 排序链表