Find Middle of Linked List
In this page:
Problem
Finding the middle node of a linked list comes up as a building block in several other algorithms, like splitting a list in half for merge sort or checking whether a list is a palindrome.
Example: Problem
#include <iostream>
using namespace std;
struct Node { int data; Node* next; };
int main() {
Node* a = new Node{1, new Node{2, new Node{3, new Node{4, new Node{5, nullptr}}}}};
cout << "finding the middle helps split a list for merge sort or palindrome checks" << endl;
return 0;
}class Node { int data; Node next; Node(int d) { data = d; } }
public class Main {
public static void main(String[] args) {
Node a = new Node(1); a.next = new Node(2); a.next.next = new Node(3);
System.out.println("finding the middle helps split a list for merge sort or palindrome checks");
}
}class Node:
def __init__(self, data):
self.data = data
self.next = None
a = Node(1); a.next = Node(2); a.next.next = Node(3)
print("finding the middle helps split a list for merge sort or palindrome checks")#include <stdio.h>
int main() {
printf("finding the middle helps split a list for merge sort or palindrome checks\n");
return 0;
}Login to try C/C++/Java code in the editor
Slow and Fast
The efficient approach uses two pointers moving at different speeds: a slow pointer that advances one node per step, and a fast pointer that advances two nodes per step, both starting from the head.
Example: Slow and Fast
#include <iostream>
using namespace std;
struct Node { int data; Node* next; };
int main() {
Node* head = new Node{1, new Node{2, new Node{3, new Node{4, new Node{5, nullptr}}}}};
Node* slow = head; Node* fast = head;
cout << "slow starts at " << slow->data << ", fast starts at " << fast->data << endl;
return 0;
}class Node { int data; Node next; Node(int d) { data = d; } }
public class Main {
public static void main(String[] args) {
Node head = new Node(1); head.next = new Node(2);
Node slow = head, fast = head;
System.out.println("slow starts at " + slow.data + ", fast starts at " + fast.data);
}
}class Node:
def __init__(self, data):
self.data = data
self.next = None
head = Node(1); head.next = Node(2)
slow = fast = head
print("slow starts at", slow.data, ", fast starts at", fast.data)#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *next; };
int main() {
struct Node *head = malloc(sizeof(struct Node)); head->data = 1;
struct Node *slow = head, *fast = head;
printf("slow starts at %d, fast starts at %d\n", slow->data, fast->data);
return 0;
}Login to try C/C++/Java code in the editor
Finding the Middle
By the time the fast pointer reaches the end of the list, the slow pointer, having covered exactly half the distance, is sitting right at the middle node, no separate length calculation needed.
Example: Finding the Middle
#include <iostream>
using namespace std;
struct Node { int data; Node* next; };
int main() {
Node* head = new Node{1, new Node{2, new Node{3, new Node{4, new Node{5, nullptr}}}}};
Node* slow = head; Node* fast = head;
while (fast && fast->next) { slow = slow->next; fast = fast->next->next; }
cout << "middle node: " << slow->data << endl;
return 0;
}class Node { int data; Node next; Node(int d) { data = d; } }
public class Main {
public static void main(String[] args) {
Node head = new Node(1); head.next = new Node(2); head.next.next = new Node(3);
head.next.next.next = new Node(4); head.next.next.next.next = new Node(5);
Node slow = head, fast = head;
while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; }
System.out.println("middle node: " + slow.data);
}
}class Node:
def __init__(self, data):
self.data = data
self.next = None
head = Node(1)
head.next = Node(2); head.next.next = Node(3)
head.next.next.next = Node(4); head.next.next.next.next = Node(5)
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
print("middle node:", slow.data)#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *next; };
int main() {
struct Node *n5 = malloc(sizeof(struct Node)); n5->data = 5; n5->next = NULL;
struct Node *n4 = malloc(sizeof(struct Node)); n4->data = 4; n4->next = n5;
struct Node *n3 = malloc(sizeof(struct Node)); n3->data = 3; n3->next = n4;
struct Node *n2 = malloc(sizeof(struct Node)); n2->data = 2; n2->next = n3;
struct Node *head = malloc(sizeof(struct Node)); head->data = 1; head->next = n2;
struct Node *slow = head, *fast = head;
while (fast && fast->next) { slow = slow->next; fast = fast->next->next; }
printf("middle node: %d\n", slow->data);
return 0;
}Login to try C/C++/Java code in the editor
Why It Works
This works because the fast pointer always covers twice the distance the slow pointer does in the same number of steps, so when fast has traveled the full length, slow has traveled exactly half of it.
Example: Why It Works
#include <iostream>
using namespace std;
int main() {
int steps = 0;
for (int fastPos = 0; fastPos < 5; fastPos += 2) steps++;
cout << "fast moves 2x speed of slow, so when fast covers full length, slow is at half: " << steps << " steps" << endl;
return 0;
}public class Main {
public static void main(String[] args) {
int steps = 0;
for (int fastPos = 0; fastPos < 5; fastPos += 2) steps++;
System.out.println("fast moves 2x speed of slow, so when fast covers full length, slow is at half: " + steps + " steps");
}
}steps = 0
fast_pos = 0
while fast_pos < 5:
fast_pos += 2
steps += 1
print("fast moves 2x speed of slow, so when fast covers full length, slow is at half:", steps, "steps")#include <stdio.h>
int main() {
int steps = 0;
for (int fastPos = 0; fastPos < 5; fastPos += 2) steps++;
printf("fast moves 2x speed, slow ends at half: %d steps\n", steps);
return 0;
}Login to try C/C++/Java code in the editor
Complexity
This slow/fast pointer approach finds the middle in a single O(n) pass through the list, using only O(1) extra space, compared to a two-pass approach that would first count the length and then walk to the midpoint.
Example: Complexity
#include <iostream>
using namespace std;
struct Node { int data; Node* next; };
int main() {
Node* head = new Node{1, new Node{2, new Node{3, nullptr}}};
Node* slow = head; Node* fast = head;
while (fast && fast->next) { slow = slow->next; fast = fast->next->next; }
cout << "found middle (" << slow->data << ") in one O(n) pass, O(1) space" << endl;
return 0;
}class Node { int data; Node next; Node(int d) { data = d; } }
public class Main {
public static void main(String[] args) {
Node head = new Node(1); head.next = new Node(2); head.next.next = new Node(3);
Node slow = head, fast = head;
while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; }
System.out.println("found middle (" + slow.data + ") in one O(n) pass, O(1) space");
}
}class Node:
def __init__(self, data):
self.data = data
self.next = None
head = Node(1); head.next = Node(2); head.next.next = Node(3)
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
print("found middle (", slow.data, ") in one O(n) pass, O(1) space")#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *next; };
int main() {
struct Node *n3 = malloc(sizeof(struct Node)); n3->data = 3; n3->next = NULL;
struct Node *n2 = malloc(sizeof(struct Node)); n2->data = 2; n2->next = n3;
struct Node *head = malloc(sizeof(struct Node)); head->data = 1; head->next = n2;
struct Node *slow = head, *fast = head;
while (fast && fast->next) { slow = slow->next; fast = fast->next->next; }
printf("found middle (%d) in O(n) pass, O(1) space\n", slow->data);
return 0;
}Login to try C/C++/Java code in the editor
🔒
Chapter Quiz — Complete all 8 topics to unlock
0/8 topics done
Complete these topics first: