algoadvance

You are given the head of a singly linked list and two integers left and right where 1 <= left <= right <= n (n is the length of the list). Reverse the nodes of the list from position left to position right, and return the reversed list.

Example:

Input:

• head = [1, 2, 3, 4, 5]
• left = 2
• right = 4

Output:

• [1, 4, 3, 2, 5]

Clarifying Questions

1. What should be returned if the left and right labels are the same?
   • The list should remain unchanged as there’s no range to reverse.
2. What is the constraint on the values within the linked list?
   • The values can be any integer within the standard signed 32-bit range.
3. Are duplicate values allowed in the linked list?
   • Yes, duplicate values are allowed.
4. Is the given list guaranteed to be non-empty?
   • Yes.

Strategy

1. Traverse the linked list to reach the node at position left.
2. Reverse the sublist from position left to right.
3. Reconnect the reversed sublist with the rest of the list.
4. Return the modified list.

Steps:

1. Use a dummy node to simplify position handling especially for corner cases.
2. Traverse the list to just before the left position.
3. Perform the sublist reversal from left to right positions.
4. Reconnect the reversed sublist back to the original list.

Code

Here’s the implementation in Python:

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:
        return None

    # Position just before the start of the to-be-reversed section
    dummy = ListNode(0)
    dummy.next = head
    prev = dummy

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

    # Reverse from left to right
    current = prev.next
    reverse = None

    for _ in range(right - left + 1):
        next_node = current.next
        current.next = reverse
        reverse = current
        current = next_node

    # Connect reversed part with the previous part
    prev.next.next = current
    prev.next = reverse

    return dummy.next

Time Complexity

• Time Complexity: O(n)
  • Where n is the number of nodes in the linked list. We traverse the list once to reach the left position and perform the reversal in a segment which takes linear time.
• Space Complexity: O(1)
  • We use a constant amount of extra space for pointers.

This ensures an optimal and efficient approach for reversing a sublist within a singly linked list.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?