19. Reverse Linked List II 🔥

Medium

Problem:

Reverse the elements from index m to n. Index m starts from 1.

Input: head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]

Solution:

The assigned start and end values do not change until the end. The tmp value is also always set to start.next.

Let's say we have m = 2, n = 5 and the linked list looks like this: root -> 1 -> 2 -> 3 -> 4 -> 5 -> 6.

• start = 1, end = 2, tmp = 2: 1 -> 3, 2 -> 4, 3 -> 2

• start = 1, end = 2, tmp = 3: 1 -> 4, 2 -> 5, 4 -> 3

• start = 1, end = 2, tmp = 4: 1 -> 5, 2 -> 6, 5 -> 4

• start = 1, end = 2, tmp = 5: 1 -> 5 -> 4 -> 3 -> 2 -> 6

class Solution:
    def reverseBetween(self, head: [ListNode], left: int, right: int) -> [ListNode]:
        if not head or left == right:
            return head
    
        root = start = ListNode(None)
        root.next = head
    
        # start, end
        for _ in range(left - 1):
            start = start.next
        end = start.next
    
        # reverse
        for _ in range(right - left):
            tmp, start.next, end.next = start.next, end.next, end.next.next
            start.next.next = tmp
    
        return root.next