AlgoViz
HomeLinked List

Delete the middle node in LL

Medium

Slow and fast, keeping the predecessor

Problem

Given the head of a non-empty singly linked list containing integers, delete the middle node of the linked list. Return the head of the modified linked list. The middle node of a linked list of size n is the (⌊n / 2⌋ + 1)^th node from the start using 1-based indexing, where ⌊x⌋ denotes the largest integer less than or equal to x.

In simple words

Use slow/fast pointers so slow lands on the middle, then unlink it.

The idea

Run the slow/fast walk but also keep the node before slow, so when slow lands on the middle you can unlink it in O(1). A one-node list has no middle to delete and returns null.

The trick

  • Track prev alongside slow, or you cannot unlink.
  • Handle the single-node list explicitly.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

1
2
3
4
5
0
1
2
3
4

Step 1 of 2. Here's the example — head -> 1 -> 2 -> 3 -> 4 -> 5 Values: 1, 2, 3, 4, 5.

1/2
Optimal
timeO(n)spaceO(1)
1if head.next == null: return null2slow = head; fast = head; prev = null3while fast and fast.next:4  fast = fast.next.next; prev = slow; slow = slow.next5prev.next = slow.next6return head

Input

array
[1, 2, 3, 4, 5]

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
list = 1 -> 2 -> 3 -> 4 -> 5
Output:
1 -> 2 -> 4 -> 5
Explanation:
The middle node 3 is removed.

Example 2

Input:
list = 1 -> 2 -> 3 -> 4
Output:
1 -> 2 -> 4
Explanation:
For even length, drop the second middle.

Example 3

Input:
list = 1
Output:
(empty)
Explanation:
One node → becomes empty.

Constraints

  • 1 <= number of nodes in the Linked List <= 10^5
  • 0 <= ListNode.val <= 10^4

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.