Middle of the Linked List

Middle of the Linked List 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.

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

• Two Pointers pattern guide
• Fixed Separation (Nth Node from End) subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to Middle of the Linked List

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

• Delete the Middle Node of a Linked List — Medium, same subpattern
• Remove Nth Node From End of List — Medium, same subpattern
• Backspace String Compare — Easy, same pattern
• Boats to Save People — Medium, same pattern
• Container With Most Water — Medium, same pattern
• Crawler Log Folder — Easy, same pattern