Middle of the Linked List solution and explanation
Google
TCS
IBM
9 more videos on this problem
Middle of the Linked List - Leetcode 876 - PythonNeetCodeIO · 4:57 · 43K views
Middle of linked list | Leetcode #876Techdose · 4:00 · 34K views
LeetCode Middle of the Linked List Solution Explained - JavaNick White · 2:51 · 31K views
Middle of a Linked List (LeetCode 876) | Full Solution with animations | Study AlgorithmsNikhil Lohia · 11:12 · 14K views
Middle of the Linked List | Hare and Tortoise | Leetcode 876codestorywithMIK · 7:01 · 11K views
Middle of the Linked List - Leetcode 876 - Linked Lists (Python)Greg Hogg · 5:46 · 8K views
[Java] Leetcode 876. Middle of the Linked List [Fast & Slow Pointers #3]Eric Programming · 5:09 · 2K views
876. Middle of the Linked List | JavaScript | Two Pointers | LeetCode 75 | Easy SolutionLeetCodeWithMonu · 5:38 · 1K views
Leetcode | 876. Middle of the Linked List | Easy | Java SolutionDeveloper Docs · 4:34 · 1K views
Middle of Linked List - LeetCode 876 - JavaScriptAlgoJS · 2:08 · 1K views
The problem
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
Approach overview
Problem Overview: Given the head of a singly linked list, return the middle node. If the list has two middle nodes (even length), return the second middle node. The task is a classic traversal problem on a linked list where you must locate the midpoint without modifying the structure.
Approach 1: List Length Calculation (O(n) time, O(1) space)
This approach performs two passes over the list. First, iterate through the entire list and count the number of nodes. Once you know the length n, compute the middle index n / 2. Then iterate again from the head until you reach that index and return the node. The idea is straightforward: determine the exact midpoint using the total size, then walk directly to it. This approach is simple to reason about and useful when the length of the list is already needed for other operations.
Approach 2: Two-pointer Technique (Slow and Fast) (O(n) time, O(1) space)
This method uses the classic two pointers technique. Initialize two pointers: slow and fast, both starting at the head. Move slow one step at a time while fast moves two steps at a time. When fast reaches the end of the list (or null), slow will be positioned exactly at the middle node. The key insight is that the fast pointer covers the list twice as quickly, so when traversal finishes, the slow pointer has completed half the distance.
This technique works naturally for both odd and even-length lists. In an even-length list, the fast pointer reaches the end while the slow pointer lands on the second middle node, which matches the problem requirement. The algorithm requires only a single traversal and constant extra memory.
Recommended for interviews: The slow–fast pointer method is the expected solution in most interviews. It demonstrates strong understanding of pointer manipulation in linked lists and shows you recognize common traversal patterns. The length-counting method is still useful as a baseline approach and proves you can reason about list structure, but the two-pointer technique highlights stronger algorithmic thinking.
Approach 1: Two-pointer Technique (Slow and Fast)
This technique uses two pointers, 'slow' and 'fast'. Both start at the head of the list. The 'slow' pointer progresses one node at a time while the 'fast' pointer moves two nodes at a time. When the 'fast' pointer reaches the end of the list, the 'slow' pointer will be at the middle node. This works because the 'fast' pointer traverses the list twice as fast as the 'slow' pointer, thus splitting the path lengthwise in half.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def middleNode(self, head: ListNode) -> ListNode:
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slowclass ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public 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;
}
}#include <iostream>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
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;
}function ListNode(val, next) {
this.val = (val===undefined ? 0 : val)
this.next = (next===undefined ? null : next)
}
var middleNode = function(head) {
let slow = head;
let fast = head;
while (fast !== null && fast.next !== null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
};#include <stdio.h>
#include <stdlib.h>
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode* middleNode(struct ListNode* head) {
struct ListNode* slow = head;
struct ListNode* fast = head;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}public class ListNode {
public int val;
public ListNode next;
public ListNode(int val = 0, ListNode next = null) {
this.val = val;
this.next = next;
}
}
public 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;
}
}Python's solution involves defining a ListNode class for the nodes of the linked list. The 'middleNode' function executes the two-pointer technique, returning the middle node when 'fast' reaches the list's end.
Time Complexity: O(n).
Space Complexity: O(1).
Approach 2: List Length Calculation
This approach involves two passes over the list. The first pass calculates the total number of nodes. In the second pass, we traverse halfway through the list to reach the middle node by stopping at n/2, where n is the number of nodes. This explicitly determines the node that marks the middle of the list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def middleNode(self, head: ListNode) -> ListNode:
length = 0
temp = head
while temp:
length += 1
temp = temp.next
halfLength = length // 2
temp = head
for _ in range(halfLength):
temp = temp.next
return tempclass ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public class Solution {
public ListNode middleNode(ListNode head) {
int length = 0;
ListNode temp = head;
while (temp != null) {
length++;
temp = temp.next;
}
int halfLength = length / 2;
temp = head;
for (int i = 0; i < halfLength; i++) {
temp = temp.next;
}
return temp;
}
}#include <iostream>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* middleNode(ListNode* head) {
int length = 0;
ListNode* temp = head;
while (temp != NULL) {
length++;
temp = temp->next;
}
int halfLength = length / 2;
temp = head;
for (int i = 0; i < halfLength; ++i) {
temp = temp->next;
}
return temp;
}function ListNode(val, next) {
this.val = (val===undefined ? 0 : val)
this.next = (next===undefined ? null : next)
}
var middleNode = function(head) {
let length = 0;
let current = head;
while (current !== null) {
length++;
current = current.next;
}
let halfLength = Math.floor(length / 2);
current = head;
for (let i = 0; i < halfLength; i++) {
current = current.next;
}
return current;
};#include <stdio.h>
#include <stdlib.h>
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode* middleNode(struct ListNode* head) {
int length = 0;
struct ListNode* temp = head;
while (temp != NULL) {
length++;
temp = temp->next;
}
int halfLength = length / 2;
temp = head;
for (int i = 0; i < halfLength; i++) {
temp = temp->next;
}
return temp;
}public class ListNode {
public int val;
public ListNode next;
public ListNode(int val = 0, ListNode next = null) {
this.val = val;
this.next = next;
}
}
public class Solution {
public ListNode MiddleNode(ListNode head) {
int length = 0;
ListNode temp = head;
while (temp != null) {
length++;
temp = temp.next;
}
int halfLength = length / 2;
temp = head;
for (int i = 0; i < halfLength; i++) {
temp = temp.next;
}
return temp;
}
}Python computes the linked list's length during a first traversal, and then advances through half the nodes to fetch the middle one for the return statement.
Time Complexity: O(n).
Space Complexity: O(1).
Approach 3: Fast and Slow Pointers
We define two pointers fast and slow, both initially pointing to the head of the linked list.
The fast pointer fast moves two steps at a time, while the slow pointer slow moves one step at a time. When the fast pointer reaches the end of the linked list, the node pointed to by the slow pointer is the middle node.
The time complexity is O(n), where n is the length of the linked list. The space complexity is O(1).
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function middleNode(head: ListNode | null): ListNode | null {
let fast = head,
slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func middleNode(head *ListNode) *ListNode {
slow, fast := head, head
for fast != nil && fast.Next != nil {
slow, fast = slow.Next, fast.Next.Next
}
return slow
}// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
// pub val: i32,
// pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
// #[inline]
// fn new(val: i32) -> Self {
// ListNode {
// next: None,
// val
// }
// }
// }
impl Solution {
pub fn middle_node(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
let mut slow = &head;
let mut fast = &head;
while fast.is_some() && fast.as_ref().unwrap().next.is_some() {
slow = &slow.as_ref().unwrap().next;
fast = &fast.as_ref().unwrap().next.as_ref().unwrap().next;
}
slow.clone()
}
}/**
* Definition for a singly-linked list.
* class ListNode {
* public $val = 0;
* public $next = null;
* function __construct($val = 0, $next = null) {
* $this->val = $val;
* $this->next = $next;
* }
* }
*/
class Solution {
/**
* @param ListNode $head
* @return ListNode
*/
function middleNode($head) {
$count = 0;
$tmpHead = $head;
while ($tmpHead != null) {
$tmpHead = $tmpHead->next;
$count++;
}
$len = $count - floor($count / 2);
while ($count != $len) {
$head = $head->next;
$count--;
}
return $head;
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Two-pointer Technique (Slow and Fast) | Time Complexity: O(n). |
| List Length Calculation | Time Complexity: O(n). |
| Fast and Slow Pointers | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| List Length Calculation | O(n) | O(1) | When simplicity is preferred or when the list length is already being computed |
| Two-pointer Technique (Slow and Fast) | O(n) | O(1) | Best general solution; single traversal and commonly expected in interviews |
Frequently asked questions
Is Middle of the Linked List easy or hard?
Middle of the Linked List is classified as an Easy problem. The logic is straightforward once you understand linked list traversal and the two-pointer technique. It is frequently used to introduce pointer-based algorithms in coding interviews.
Middle of the Linked List Python/Java solution
Most solutions in Python and Java implement the slow–fast pointer approach. Two references move through the list at different speeds until the fast pointer reaches the end. The node referenced by the slow pointer is returned as the middle element.
How to solve Middle of the Linked List in O(n)?
Use the slow and fast pointer strategy. Initialize both pointers at the head of the linked list. Move slow by one node and fast by two nodes each iteration. When the fast pointer reaches the end or becomes null, the slow pointer will point to the middle node.
What is the best approach for Middle of the Linked List?
The slow and fast two-pointer technique is the best approach. Move one pointer one step at a time and another two steps at a time. When the fast pointer reaches the end, the slow pointer will be at the middle node. This runs in O(n) time with O(1) extra space and requires only a single traversal.
Is Middle of the Linked List asked at Google/Amazon/Meta?
Middle of the Linked List is a common warm-up question in technical interviews and appears in interview preparation sets used by companies like Amazon, Google, and Meta. It tests understanding of linked list traversal and pointer manipulation rather than complex algorithms.
What data structure is used in Middle of the Linked List?
The problem uses a singly linked list data structure. Nodes are connected through pointers rather than stored in contiguous memory like arrays, so traversal must follow node references to locate the middle.
What is the time complexity of Middle of the Linked List?
The optimal solution runs in O(n) time because the list is traversed once. Space complexity is O(1) since only two pointers are used regardless of input size. Even the length-counting method remains O(n) time but requires two passes over the list.