Practice › Linked List
Middle of a Linked List
Easy · Linked List · Asked at Amazon, Microsoft, TCS, Infosys, Wipro
Print the value of the middle node. If there are two middle nodes, print the second one.
Input
First line: n. Second line: the n node values from head to tail.
Output
The middle value.
Constraints
- 1 ≤ n ≤ 10^5
Slow and fast pointers: when fast reaches the end, slow is at the middle.
Example 1
Input
5 1 2 3 4 5
Output
3
Example 2
Input
6 1 2 3 4 5 6
Output
4
Hints
- Counting the nodes and walking n/2 steps takes two passes. Can you do it in one?
- Move slow by 1 and fast by 2. When fast can't move any more, slow is at the middle.
Approach
Tortoise and hare. Both start at head. While fast and fast.next exist, move slow = slow.next and fast = fast.next.next. Fast covers twice the distance, so slow ends at the middle. For an even length it stops on the second middle node, which is what's asked.
Complexity: O(n) time · O(1) extra space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
struct Node {
long long val;
Node *next;
Node(long long v) : val(v), next(nullptr) {}
};
int main() {
int n;
cin >> n;
Node dummy(0), *tail = &dummy;
for (int i = 0; i < n; i++) {
long long v;
cin >> v;
tail = tail->next = new Node(v);
}
Node *slow = dummy.next, *fast = dummy.next;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
cout << slow->val << "\n";
return 0;
}Python solution
import sys
class Node:
def __init__(self, val, nxt=None):
self.val, self.next = val, nxt
data = sys.stdin.read().split()
n = int(data[0])
head = None
for v in reversed(data[1 : n + 1]):
head = Node(v, head)
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
print(slow.val)Java solution
import java.util.*;
public class Main {
static class Node {
long val;
Node next;
Node(long v) { val = v; }
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
Node dummy = new Node(0), tail = dummy;
for (int i = 0; i < n; i++) tail = tail.next = new Node(sc.nextLong());
Node slow = dummy.next, fast = dummy.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
System.out.println(slow.val);
}
}Solve Middle of a Linked List online · All practice problems