2095. Delete the Middle Node of a Linked List


Problem Description

You have a singly linked list. Your task is to remove the node that is in the middle of this list and return the head of the updated list. The middle node is defined as the &lfloor;n / 2&rfloor;<sup>th</sup> node from the beginning of the list, where n is the total number of nodes in the list and &lfloor;x&rfloor; signifies the greatest integer less than or equal to x. This means that you're not counting from 1, but from 0. So, in a linked list with:

  • 1 node, the middle is the 0th node.
  • 2 nodes, the middle is the 1st node.
  • 3 nodes, the middle is the 1st node.
  • 4 nodes, the middle is the 2nd node.
  • 5 nodes, the middle is the 2nd node.

Your goal is to efficiently find and remove this middle node and ensure the integrity of the linked list is maintained after the removal.

Intuition

To solve this problem, the two-pointer technique is a perfect fit. The idea is to have two pointers, slow and fast. The slow pointer moves one step at a time, while the fast pointer moves two steps at a time. By the time the fast pointer reaches the end of the list, the slow pointer will be at the middle node.

Here's the step-by-step intuition:

  1. Initialize a dummy node that points to the head. This dummy node will help us easily handle edge cases like when there's only one node in the list.
  2. Start both slow and fast pointers. The slow pointer will start from the dummy node, while fast will start from the head node of the list.
  3. Move slow one step and fast two steps until fast reaches the end of the list or has no next node (this is for cases when the number of nodes is even).
  4. When the fast pointer reaches the end of the list, the slow pointer will be on the node just before the middle node (since it started from dummy, which is before the head).
  5. Adjust the next pointer of the slow node so that it skips over the middle node, effectively removing it from the list.
  6. Return the new head of the list, which is pointed to by dummy.next, since the dummy node was added before the original head.

By utilizing this approach, we can identify and remove the middle node in a singly linked list in a single pass and O(n) time complexity, where n is the number of nodes in the list.

Learn more about Linked List and Two Pointers patterns.

Solution Approach

The solution utilizes a two-pointer approach, which is a common technique for problems involving linked lists or arrays where elements need to be compared or modified based on their positions. Here's a detailed walk-through:

  1. Initialization: A dummy node is created and set to point to the head of the list. The dummy node, not present in the original list, serves as a starting point for the slow pointer, and helps in case the list has only one node, or if we need to delete the head of the list.

  2. Two-Pointers: Two pointers are defined: slow starting at the dummy node and fast at the head node. This offset will allow slow to reach the node just before the middle node by the time fast reaches the end.

  3. Traversal: The traversal begins with a while loop that continues until fast is neither null nor pointing to a node with a null next pointer. Inside the loop:

    • The slow pointer is moved one node forward with slow = slow.next.
    • The fast pointer is moved two nodes forward with fast = fast.next.next.
  4. Deletion: After the loop, slow is at the node just before the middle node. To delete the middle node, slow.next is updated to point to slow.next.next. This effectively removes the middle node from the list by "skipping" it, as it is no longer referenced by the previous node.

  5. Return Updated List: Finally, the head of the updated list is returned, which is dummy.next. This is because dummy is a pseudo-head pointing to the actual head of the list and its next pointer reflects the head of the updated list post-deletion.

The key data structure used is the singly-linked list, which is manipulated using pointer operations. This solution ensures that the middle node is deleted in a single pass, with a time complexity of O(n), where n is the number of nodes in the list. There is a constant space complexity of O(1), as the number of new variables used does not scale with the input size.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

Example Walkthrough

Let's illustrate the solution approach using a small example. Suppose we have the following linked list:

1[ A ] -> [ B ] -> [ C ] -> [ D ] -> [ E ]

We want to remove the &lfloor;5 / 2&rfloor; = 2nd node from the beginning, which in this case is node [ C ].

Following the solution approach:

Step 1: Initialization

  • We create a dummy node [ X ] and point it to the head of the list [ A ].
  • The list now looks like this: [ X ] -> [ A ] -> [ B ] -> [ C ] -> [ D ] -> [ E ].

Step 2: Two-Pointers

  • We set the slow pointer to [ X ] (dummy node) and the fast pointer to [ A ] (head node).

Step 3: Traversal

  • We start moving both pointers through the list with the loop condition in mind.
1First iteration:
2  [ X ] -> [ A ] -> [ B ] -> [ C ] -> [ D ] -> [ E ]
3     ↑                   ↑
4    slow                fast
5
6Second iteration:
7  [ X ] -> [ A ] -> [ B ] -> [ C ] -> [ D ] -> [ E ]
8               ↑                            ↑
9              slow                         fast
10
11Third iteration (fast.next is null):
12  [ X ] -> [ A ] -> [ B ] -> [ C ] -> [ D ] -> [ E ]
13                       ↑                                   ↑
14                      slow                                fast (end of list)

Step 4: Deletion

  • Now that fast has reached the end of the list, slow is just before the node we want to delete ([ C ]).
  • We perform the deletion by updating the next pointer of the slow node to skip [ C ] and point to [ slow.next.next ].
1Before deletion:
2  [ X ] -> [ A ] -> [ B ] -> [ C ] -> [ D ] -> [ E ]
3                       ↑               ↑
4                      slow           slow.next (to be deleted)
5
6After deletion:
7  [ X ] -> [ A ] -> [ B ] ----------> [ D ] -> [ E ]
8                       ↑                            ↑
9                      slow                       slow.next

Step 5: Return Updated List

  • We return the head of the updated list, which is dummy.next.
  • The final updated list looks like this:
1[ A ] -> [ B ] -> [ D ] -> [ E ]

Node [ C ] has been removed, and the integrity of the list is maintained.

Solution Implementation

1# Definition for singly-linked list.
2class ListNode:
3    def __init__(self, val=0, next=None):
4        self.val = val
5        self.next = next
6
7class Solution:
8    def deleteMiddle(self, head: Optional[ListNode]) -> Optional[ListNode]:
9        # Create a dummy node that points to the head of the list, to handle edge cases smoothly
10        dummy_node = ListNode(next=head)
11      
12        # Initialize two pointers, slow will move one step at a time, fast will move two steps at a time
13        slow_pointer, fast_pointer = dummy_node, head
14      
15        # Iterate through the list to find the middle
16        while fast_pointer and fast_pointer.next:
17            slow_pointer = slow_pointer.next  # Move slow pointer one step
18            fast_pointer = fast_pointer.next.next  # Move fast pointer two steps
19      
20        # Now, slow_pointer is at the node just before the middle one. Delete the middle node
21        slow_pointer.next = slow_pointer.next.next
22      
23        # Return the head of the updated list, by skipping over the dummy node
24        return dummy_node.next
25
1// Definition of a singly-linked list node.
2class ListNode {
3    int value;
4    ListNode next;
5
6    ListNode() {}
7    ListNode(int value) { this.value = value; }
8    ListNode(int value, ListNode next) {
9        this.value = value;
10        this.next = next;
11    }
12}
13
14class Solution {
15    public ListNode deleteMiddle(ListNode head) {
16        // Create a dummy node that acts as a predecessor of the head node.
17        ListNode dummy = new ListNode(0, head);
18        // Initialize two pointers, slow and fast. Slow moves 1 node at a time, while fast moves 2 nodes.
19        ListNode slow = dummy, fast = head;
20      
21        // Iterate through the list with the fast pointer advancing twice as fast as the slow pointer
22        // so that when the fast pointer reaches the end, the slow pointer will be at the middle.
23        while (fast != null && fast.next != null) {
24            slow = slow.next; // Move slow pointer one step.
25            fast = fast.next.next; // Move fast pointer two steps.
26        }
27      
28        // Skip the middle node. Slow pointer now points to the node before the middle node.
29        slow.next = slow.next.next;
30
31        // Return the modified list. The dummy's next points to the new list's head.
32        return dummy.next;
33    }
34}
35
1/**
2 * Definition for singly-linked list.
3 * struct ListNode {
4 *     int value;
5 *     ListNode *next;
6 *     ListNode(int value = 0) : value(value), next(nullptr) {}
7 *     ListNode(int value, ListNode *next) : value(value), next(next) {}
8 * };
9 */
10class Solution {
11public:
12    // Function to delete the middle node of the linked list.
13    ListNode* deleteMiddle(ListNode* head) {
14        // Create a dummy node that points to the head of the list.
15        ListNode* dummyNode = new ListNode(0, head);
16      
17        // Initialize slow and fast pointers for the runner technique.
18        ListNode* slowPointer = dummyNode;
19        ListNode* fastPointer = head;
20
21        // Advance the fast pointer by two steps and the slow pointer by one step
22        // until fast reaches the end of the list.
23        while (fastPointer && fastPointer->next) {
24            slowPointer = slowPointer->next;          // Move slow pointer by one
25            fastPointer = fastPointer->next->next;    // Move fast pointer by two
26        }
27
28        // The slow pointer now points at the node before the middle node.
29        ListNode* toDelete = slowPointer->next;       // Store the middle node to delete  
30        slowPointer->next = slowPointer->next->next;  // Remove the middle node
31
32        delete toDelete; // Free memory of the node to be deleted
33
34        // The head of the new modified list is the next node of dummyNode.
35        ListNode* newHead = dummyNode->next;
36        delete dummyNode; // Delete the dummyNode to prevent memory leak
37
38        return newHead; // Return the new head of the list
39    }
40};
41
1/**
2 * Deletes the middle node of a singly linked list.
3 * If the list is empty or has only one node, returns null.
4 * If the list has an even number of nodes, it removes the second of the two middle nodes.
5 * @param head - The head node of the singly linked list.
6 * @returns The head node of the modified list with the middle node removed.
7 */
8
9function deleteMiddle(head: ListNode | null): ListNode | null {
10    // If the list is empty or has only one node, it means there is no middle to delete.
11    if (!head || !head.next) {
12        return null;
13    }
14
15    let fast: ListNode | null = head.next; // This pointer will move at twice the speed of 'slow'.
16    let slow: ListNode = head; // This pointer will move one step at a time.
17
18    // Move through the list until 'fast' reaches the last or the second to last node.
19    while (fast.next && fast.next.next) {
20        slow = slow.next; // Move 'slow' one step.
21        fast = fast.next.next; // Move 'fast' two steps.
22    }
23
24    // 'slow' is now behind the middle node, so set its 'next' to skip the middle node.
25    slow.next = slow.next.next;
26
27    // Return the modified list with the middle node removed.
28    return head;
29}
30

Time and Space Complexity

Time Complexity

The provided code implements an algorithm to delete the middle node of a singly-linked list. The while loop iterates through the list with two pointers: slow moves one step at a time, and fast moves two steps at a time. This loop will continue until fast (or its successor fast.next) reaches the end of the list. This means that we traverse the list only once, which leads to a time complexity of O(N), where N is the number of nodes in the singly-linked list.

Space Complexity

The algorithm uses a few constant extra variables: dummy, slow, and fast. Regardless of the size of the list, the space used by these variables does not increase. Therefore, the space complexity of the algorithm is O(1), indicating that it uses a constant amount of additional space beyond the input list.

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


🪄