AlgoMaster Logo

Middle of the Linked List

Ashish

Ashish Pratap Singh

easy

Problem Description

Solve it on LeetCode

Approaches

1. Counting the Number of Nodes

Intuition:

To find the middle of a linked list, one straightforward approach is to count the total number of nodes in the list first, and then iterate through the list again to find the node at the n/2 position, where n is the total number of nodes.

Steps:

  1. Traverse the linked list to count the total number of nodes.
  2. Calculate the index of the middle node, which is n/2 using integer division for even numbers (the middle is the second middle node).
  3. Traverse the list again up to this middle index.
  4. Return the middle node.

Code:

2. Two Pointers Technique

Intuition:

The two-pointer technique is often very efficient for linked list problems. We can use two pointers, slow and fast, to identify the middle of the list. The fast pointer moves twice as fast as the slow pointer. By the time the fast pointer reaches the end of the list, the slow pointer will be at the middle.

Steps:

  1. Initialize two pointers: slow and fast, both starting at the head of the list.
  2. Move the slow pointer by one node and the fast pointer by two nodes in each iteration.
  3. Continue moving the pointers until fast reaches the end of the list or the node just before the end (in case of even length).
  4. The slow pointer will be at the middle of the list when the loop terminates.
  5. Return the node at the slow pointer.

Visualization:

Odd Length
slow
1
fast
2
3
4
5
null
1
slow
2
3
fast
4
5
null
1
2
slow
3
4
5
fast
null
Result: Middle = 3 (slow pointer)
Even Length
slow
1
fast
2
3
4
null
1
slow
2
3
fast
4
null
1
2
slow
3
4
null
Result: Middle = 3 (slow pointer)

Code:

Prev:

Next: