We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Reverse Linked List II

Difficulty: Medium

Problem Description

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.

Key Insights

  • The problem requires reversing a portion of a linked list between two specified positions.
  • The reversal should be done in-place, meaning we should not use extra space for another linked list.
  • We need to handle edge cases, such as when left and right are the same, which means no reversal is needed.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes in the linked list, as we will traverse the list once. Space Complexity: O(1), since we are reversing the nodes in-place and not using any additional data structures for storage.

Solution

To solve the problem, we can use a three-step approach:

  1. Traverse the linked list to reach the node just before the left position. This will help us to connect the reversed portion back to the original list.
  2. Reverse the nodes from position left to right. We will maintain the pointers to reverse the nodes iteratively.
  3. Connect the reversed portion back to the original list and return the modified list.

The main data structure used here is the linked list, and the algorithmic approach is a two-pointer technique to facilitate the reversal.

Code Solutions

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverseBetween(head: ListNode, left: int, right: int) -> ListNode:
    if not head or left == right:
        return head

    # Create a dummy node to simplify edge cases
    dummy = ListNode(0)
    dummy.next = head
    prev = dummy

    # Move `prev` to the node before the `left` position
    for _ in range(left - 1):
        prev = prev.next

    # Start reversing
    curr = prev.next
    tail = curr  # This will be the tail after reversal
    prev_reverse = None

    for _ in range(right - left + 1):
        next_temp = curr.next  # Store next node
        curr.next = prev_reverse  # Reverse the link
        prev_reverse = curr  # Move prev_reverse to current
        curr = next_temp  # Move to the next node

    # Connect the reversed part back to the list
    prev.next = prev_reverse
    tail.next = curr

    return dummy.next
← Back to All Questions