One pass
We jump to the left node and reverse (right-left+1) number of nodes. We then fix two pointers:
- prev -> reversed_head
- reversed_tail -> next

To simplify the (prev, curr) logic we introduce a dummy node.

Time: , space:
.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverse(self, head, reverse_count):
prev, curr = None, head
while reverse_count > 0:
next = curr.next
curr.next = prev
prev = curr
curr = next
reverse_count -= 1
return prev, curr
def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
dummy = ListNode(next=head)
jump_count = left-1
prev, curr = dummy, head
while jump_count > 0:
prev = curr
curr = curr.next
jump_count -= 1
reverse_count = right-left+1
reversed_head, next_head = self.reverse(curr, reverse_count)
curr.next = next_head
prev.next = reversed_head
return dummy.next
Leave a comment