Problem Statement
leetcode problem link
My Solution [Accepted]
# 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]:
sentinel = ListNode(-1, head)
slow = sentinel
fast = sentinel.next
middleNode = slow.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
middleNode = slow.next
prev = sentinel
curr = head
while curr is not None:
if curr is middleNode:
prev.next = curr.next
break
prev = curr
curr = curr.next
return sentinel.next
Editorial
Approach 1: 2 Passes
class Solution:
def deleteMiddle(self, head: Optional[ListNode]) -> Optional[ListNode]:
# Edge case: return None if there is only one node.
if head.next == None:
return None
count = 0
p1 = p2 = head
# First pass, count the number of nodes in the linked list using 'p1'.
while p1:
count += 1
p1 = p1.next
# Get the index of the node to be deleted.
middle_index = count // 2
# Second pass, let 'p2' move toward the predecessor of the middle node.
for _ in range(middle_index - 1):
p2 = p2.next
# Delete the middle node and return 'head'.
p2.next = p2.next.next
return head
Approach 2: Fast and Slow Pointers
class Solution:
def deleteMiddle(self, head: Optional[ListNode]) -> Optional[ListNode]:
# Edge case: return None if there is only one node.
if head.next == None:
return None
# Initialize two pointers, 'slow' and 'fast'.
slow, fast = head, head.next.next
# Let 'fast' move forward by 2 nodes, 'slow' move forward by 1 node each step.
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# When 'fast' reaches the end, remove the next node of 'slow' and return 'head'.
slow.next = slow.next.next
# The job is done, return 'head'.
return head