Delete the Middle Node of a Linked List

Problem

You are given the head of a linked list. Delete the middle node, and return the head of the modified linked list.

The middle node of a linked list of size n is the ⌊n / 2⌋th node from the start using 0-based indexing, where ⌊x⌋ denotes the largest integer less than or equal to x.

• For n = 1, 2, 3, 4, and 5, the middle nodes are 0, 1, 1, 2, and 2, respectively.

Examples

Example 1:

graph LR;
A(1) --> B(3) --> C(4) --> D(7) --> E(1) --> F(2) --> G(6)
style D fill:#f9f

Input: head = [1,3,4,7,1,2,6]
Output: [1,3,4,1,2,6]
Explanation:
The above figure represents the given linked list. The indices of the nodes are written below.
Since n = 7, node 3 with value 7 is the middle node, which is marked in red.
We return the new list after removing this node. 

Example 2:

graph LR;
A(1) --> B(2) --> C(3) --> D(4)
style C fill:#f9f

Input: head = [1,2,3,4]
Output: [1,2,4]
Explanation:
The above figure represents the given linked list.
For n = 4, node 2 with value 3 is the middle node, which is marked in red.

Example 3:

graph LR;
A(2) --> B(1)
style B fill:#f9f

Input: head = [2,1]
Output: [2]
Explanation:
The above figure represents the given linked list.
For n = 2, node 1 with value 1 is the middle node, which is marked in red.
Node 0 with value 2 is the only node remaining after removing node 1.

Solution

Method 1 - Two Pass - First find length of list and then go to middle

We first calculate the length of the linked list using [Find the length of the linked list](find-the-length-of-the-linked-list), lets call it n. Then loop till n/2 and remove the n/2 th node.

Complexity

• ⏰ Time complexity: O(n), where n is the length of the linked list.
• 🧺 Space complexity: O(1)

Method 2 - Slow and Fast Pointer

This problem is similar to [Middle of the linked list](middle-of-the-linked-list), but here we need to modify the list, so we need prev pointer, and hence we need dummy pointer.

We can follow following steps:

1. Create a dummy head, and initialize slow and fast pointers as dummy;
2. Traverse the ListNodes starting from dummy by the afore-mentioned two pointers, slow forwards 1 step and fast forwards 2 steps per iteration;
3. Terminate the traversal till fast.next or fast.next.next is null, and now slow points to the previous node of the middle node; remove the middle node;
4. Return dummy.next as the result.

Code

Java

class Solution {

	public ListNode deleteMiddle(ListNode head) {
		ListNode dummy = new ListNode(-1), slow = dummy, fast = dummy;
		dummy.next = head;

		while (fast.next != null && fast.next.next != null) {
			slow = slow.next;
			fast = fast.next.next;
		}

		slow.next = slow.next.next;
		return dummy.next;
	}
}

Complexity

• ⏰ Time complexity: O(n), where n is the length of the linked list.
• 🧺 Space complexity: O(1)

Method 3 - Slow and Fast with prev pointer

Add a prev pointers following slow one.

Code

Java

class Solution {

	public ListNode deleteMiddle(ListNode head) {
		ListNode dummy = new ListNode(-1), prev = dummy, slow = head, fast = head;
		prev.next = head;

		while (fast != null && fast.next != null) {
			prev = slow;
			slow = slow.next;
			fast = fast.next.next;
		}

		prev.next = slow.next;
		return dummy.next;
	}
}

Complexity

• ⏰ Time complexity: O(n), where n is the length of the linked list.
• 🧺 Space complexity: O(1)