1
# Definition for singly-linked list.
2
# class ListNode:
3
#     def __init__(self, val=0, next=None):
4
#         self.val = val
5
#         self.next = next
6
class Solution:
7
    def reverseBetween(
8
        self, head: Optional[ListNode], left: int, right: int
9
    ) -> Optional[ListNode]:
10
        # revrese api
11
        def reverse(start, end):
12
            prev = None
13
            cur = start
14
            while prev != end:
15
                nextNode = cur.next
16
                cur.next = prev
17
                prev = cur
18
                cur = nextNode
19
            return prev
20

21
        if not head or not head.next or right <= left:
22
            return head
23

24
        start, end = head, head
25
        node, afterRight = 0, 0
26

27
        # At the begining
28
        if left == 1:
29
            # start index
30
            inc = left - 1
31
            while inc > 0:
32
                start = start.next
33
                inc -= 1
34
            # end index
35
            inc = right - 1
36
            while inc > 0:
37
                end = end.next
38
                inc -= 1
39
            afterRight = end.next
40
            reverse(start, end)
41
            head = end
42
        else:  # Left other then begining
43
            # start index
44
            inc = left - 2
45
            while inc > 0:
46
                start = start.next
47
                inc -= 1
48
            # end index
49
            inc = right - 1
50
            while inc > 0:
51
                end = end.next
52
                inc -= 1
53
            afterRight = end.next
54
            begin = start  # node before left
55
            start = start.next
56
            reverse(start, end)
57
            begin.next = end
58

59
        # If their's ll chain left agter right chain it to the updated ll
60
        if afterRight:
61
            start.next = afterRight
62

63
        return head
64

65

66
"""
67
TC : O(n)
68
Sc : O(1)
69

70
"""