Leetcode 0092. Reverse Linked List II

Problem statement

https://leetcode.com/problems/reverse-linked-list-ii/

Solution

Very similar to problem 25. We keep three pointers as with any other reverse linked lists problems: pre, curr, next. We can split all algorithm into 3 steps:

1. Do m-1 steps to reach the first point of range we need to reverse.
2. Reverse range [n - m], using 3 pointers approach.
3. Finally we need to fix connections for the start and for the end of reversed list, using saved pointer to pre element.

Complexity

Time complexity is O(n), because we need to traverse elements upto n-th. Space complexity is O(1).

Code

class Solution:
    def reverseBetween(self, head, m, n):
        if m == n: return head
        dummy = ListNode(0)
        dummy.next = head
        pre = dummy
        for i in range(m-1):
            pre = pre.next
            
        curr = pre.next
        nxt = curr.next
        
        for i in range(n-m):
            tmp = nxt.next
            nxt.next = curr
            curr = nxt
            nxt = tmp
            
        pre.next.next = nxt
        pre.next = curr
        return dummy.next