Challenge
Given the head of a singly linked list and two integers, reverse the nodes of the list from position left to position right.
E.g: reverseBetween(head, 2, 4)
1 -> 2 -> 3 -> 4 -> 5
Returns
1 -> 4 -> 3 -> 2 -> 5
Solution
class Solution:
def reverse(self, head, steps):
tmp = head
prev = None
tail = head
i = 0
while tmp and i < steps:
current = tmp
n = current.next
current.next = prev
prev = current
tmp = n
i+=1
head = current
tail.next =n
t = head
return head
def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
tmp=head
j = 1
prev = None
if right -left ==0:
return head
while tmp and j < left:
prev = tmp
tmp=tmp.next
j =j+1
a = self.reverse(tmp, right+1 - left)
if not prev:
return a
prev.next = a
return head
Time complexity: O(n)
Space complexity: 1