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, 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 Problem, 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)