Reverse Linked List-2

Introduction

Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.

Solutions

1. Using recursion

To reverse a linked list using recursion, we create a function named reverse. This function takes two parameters: node, the current node being processed, and prev, which points to the previous node. We start the recursion from the head of the list and call the reverse() function recursively.

Here's the implementation:

recursion.py

def reverse_linked_list_ii(head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
    # If the list is empty or the left and right positions are the same, no changes are needed
    if not head or (left == right):
        return head

    # 'root' is a dummy node that references the very beginning of the list
    # 'start' node will be a node that points to the first node being reversed.
    root = start = ListNode(None)
    root.next = head

    # Move 'start' to the node immediately before the reversal starts
    for _ in range(left - 1):
        start = start.next

    # 'end' will point to the first node to be reversed.
    # 'end' will be named as such because it will literally be the 'end' of reversed list
    end = start.next

    # Perform the reversal between 'left' and 'right'
    for _ in range(right - left):
        moving = end.next
        end.next = moving.next
        moving.next = start.next
        start.next = moving
    return root.next

Introduction

Solutions

1. Using recursion

References