Problem Statement
leetcode problem link
Brute Force [Accepted]
class Solution:
def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
dummy = ListNode(-1, head)
curr = dummy
left_node = right_node = curr
prev_left = next_right = curr
for _ in range(left):
prev_left = curr
curr = curr.next
left_node = curr
curr = head
for _ in range(right):
right_node = curr
curr = curr.next
next_right = right_node.next
curr = left_node
prev = None
while curr and curr is not next_right:
next_node = curr.next
curr.next = prev
prev = curr
curr = next_node
if prev_left and prev_left is not right_node:
prev_left.next = right_node
if left_node and left_node is not next_right:
left_node.next = next_right
return dummy.next
Editorial
Approach 2: Iterative Link Reversal.
class Solution:
def reverseBetween(
self, head: Optional[ListNode], m: int, n: int
) -> Optional[ListNode]:
# Empty list
if not head:
return None
# Move the two pointers until they reach the proper starting point
# in the list.
cur, prev = head, None
while m > 1:
prev = cur
cur = cur.next
m, n = m - 1, n - 1
# The two pointers that will fix the final connections.
tail, con = cur, prev
# Iteratively reverse the nodes until n becomes 0.
while n:
third = cur.next
cur.next = prev
prev = cur
cur = third
n -= 1
# Adjust the final connections as explained in the algorithm
if con:
con.next = prev
else:
head = prev
tail.next = cur
return head
