Given a singly linked list and a left and right index, reverse the nodes between the two indicies and return the modified list. How do we do this?
First we maintain a curr pointer and iteratively move the curr pointer to the first index, left. While we do this, we maintain a prev pointer to the node before the left index. This is important because we eventually need to relink the reversed segment of the linked list.
We create two more pointers, tail and conn. The tail points to curr, as curr will be the tail of the reversed segment. The conn points to prev, the node that will complete the connection from the head of the list to the reversed segment.
We conduct our standard linked list reversal for the segment, iterating in the range between right - left + 1.
Finally, we check to see if the conn pointer is None. If so, we know that prev was None before the reversal of the linked list segment. Now prev points to the beginning of the reversed linked list segment. Therefore, we set prev to head. Otherwise, we set conn.next to prev.
The tail pointer still points to the last node of the reversed linked list segment. We can now set its .next pointer to curr, as curr now points to the node after the reversed segment.
The solution is as follows:
class Solution:
def reverseBetween(
self, head: Optional[ListNode], left: int, right: int
) -> Optional[ListNode]:
prev = None
curr = head
for i in range(left - 1):
prev = curr
curr = curr.next
tail, conn = curr, prev
for j in range(right - left + 1):
next_node = curr.next
curr.next = prev
prev = curr
curr = next_node
if conn:
conn.next = prev
else:
head = prev
tail.next = curr
return head_ Time Complexity:
O(n) - We traverse all nodes within the linked list.
_ Space Complexity:
O(1) - We maintain pointers which occupy constant space.