876. Middle of the Linked List

Middle of the Linked List (LeetCode 876) is a Easy Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Two Pointers pattern, in the Fixed Separation (Nth Node from End) subpattern.

How to solve Middle of the Linked List

Middle of the Linked List is a Fixed Separation problem, part of Two Pointers. Master fixed separation two pointers to find nth node from end, middle of list, and similar problems.

Work towards the solution in these steps:

  1. Consider using pointers to traverse the linked list efficiently instead of relying on additional data structures like arrays.
  2. Think about how you can use two pointers moving at different speeds to find the middle node in a single pass.
  3. Try initializing one pointer to move twice as fast as the other; observe what happens when the faster pointer reaches the end of the list.

The reference solution runs in O(n) time and O(1) space.

The Middle of the Linked List solution and editorial walks through the full approach with reference code.

Problem statement

Given the head of a singly linked list, return the middle node of the linked list.

If there are two middle nodes, return the second middle node.

Example 1:

Input: head = [1,2,3,4,5] Output: [3,4,5] Explanation: The middle node of the list is node 3.

Example 2:

Input: head = [1,2,3,4,5,6] Output: [4,5,6] Explanation: Since the list has two middle nodes with values 3 and 4, we return the second one.

Constraints:

- The number of nodes in the list is in the range [1, 100].

- 1 <= Node.val <= 100

Topics and companies

Topics: Linked List, Two Pointers.

Reported in interviews at Microsoft.

How to practise Middle of the Linked List on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(1) space.

Open Middle of the Linked List in the code editor, or read the Middle of the Linked List editorial for a worked solution with its approach and complexity analysis.

Where Middle of the Linked List sits in the DSA pattern sheet

Problems related to Middle of the Linked List

Other problems that use the same Fixed Separation (Nth Node from End) and Two Pointers techniques:

Middle of the Linked List FAQ

What is the LeetCode number of Middle of the Linked List?

Middle of the Linked List is LeetCode problem 876, rated Easy.

What pattern is used to solve Middle of the Linked List?

Middle of the Linked List is a Fixed Separation problem. It belongs to the Two Pointers pattern, in the Fixed Separation (Nth Node from End) subpattern.

What is the time complexity of Middle of the Linked List?

The reference solution runs in O(n) time and O(1) space.

Which companies ask Middle of the Linked List?

Middle of the Linked List has been reported in interviews at Microsoft.

Preparing this workspace.