Grokking the Coding Interview: Patterns for Coding Questions
Ask Author
Back to course home

0% completed

Vote For New Content
Solution: Middle of the LinkedList
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Problem Statement

Given the head of a Singly LinkedList, write a method to return the middle node of the LinkedList.

If the total number of nodes in the LinkedList is even, return the second middle node.

Example 1:

Input: 1 -> 2 -> 3 -> 4 -> 5 -> null
Output: 3

Example 2:

Input: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null
Output: 4

Example 3:

Input: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> null
Output: 4

Constraints:

  • The number of nodes in the list is in the range [1, 100].
  • 1 <= Node.val <= 100

Solution

One brute force strategy could be to first count the number of nodes in the LinkedList and then find the middle node in the second iteration. Can we do this in one iteration?

We can use the Fast & Slow pointers method such that the fast pointer is always twice the nodes ahead of the slow pointer. This way, when the fast pointer reaches the end of the LinkedList, the slow pointer will be pointing at the middle node.

let's visualize example 3 via the below diagram.

Image

Code

Here is what our algorithm will look like:

Python3
Python3
. . . .

Complexity Analysis

Time Complexity

  • Two-pointer traversal: The algorithm uses two pointers (slow and fast). The slow pointer moves one step at a time, while the fast pointer moves two steps at a time. This allows the fast pointer to reach the end of the linked list when the slow pointer is at the middle.
  • Since both pointers traverse the list linearly, each node is visited once. The total time complexity is O(N), where N is the number of nodes in the linked list.

Overall time complexity: O(N).

Space Complexity

  • The algorithm uses only two pointers (slow and fast), and these pointers require constant space. No additional data structures are used that depend on the input size.

Overall space complexity: O(1) (constant space).

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible