MediumNo. 2095

Delete the Middle Node of a Linked List — LeetCode 2095 Python Solution

Topics
Linked List, Two Pointers
On a study list
LeetCode 75
Reading time
3 min

The problem

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

Example

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.

Python solution

PythonSolution
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteMiddle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(next=head)
        slow, fast = dummy, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        slow.next = slow.next.next
        return dummy.next

Complexity

Time
O(n)where n is the length of the list
Space · auxiliary
O(1)

Pattern: Linked List

Rewire pointers in place, with a dummy head and a saved next to keep it safe. LeetCode 2095. Delete the Middle Node of a Linked List is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Linked List.

The linked list guide has the Python template for the pattern and the 75 LeetCode problems that use it.

Related problems

Related problems
No.ProblemDifficulty
0019Remove Nth Node From End of ListMedium
0061Rotate ListMedium
0082Remove Duplicates from Sorted List IIMedium
0086Partition ListMedium
0148Sort ListMedium
0876Middle of the Linked ListEasy

Frequently asked questions

How hard is LeetCode 2095. Delete the Middle Node of a Linked List?

LeetCode 2095. Delete the Middle Node of a Linked List is rated Medium on LeetCode.

What is the time complexity of LeetCode 2095. Delete the Middle Node of a Linked List?

The Python solution on this page runs in O(n), where n is the length of the list.

What is the space complexity of LeetCode 2095. Delete the Middle Node of a Linked List?

The Python solution on this page uses O(1) auxiliary space.

What topics does LeetCode 2095. Delete the Middle Node of a Linked List cover?

LeetCode 2095. Delete the Middle Node of a Linked List is tagged Linked List and Two Pointers on LeetCode.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Free to download. Check it runs on your machine, then pick a plan.