Reverse Linked List II

---

Intuition

• With these sort of problems, always draw by hand the following cases:
  • 1 node
    • Also index [1, 1]
  • 2 nodes
  • multiple nodes
• The point of the problem is to reverse a certain part of the linked list, keeping all other nodes intact.
• This means you must remember the left and right halves that you do not reverse.
• To remember these, keep a pointer to the point just before the beginning of what you must reverse (I called that lp for left partition).
• Then, reverse up until right as you did with Reverse Linked List.
• At the end, lp must connect to itr (one past end of the linked list which could be None), and prev (now meaning the end of the reversal, i.e. the beginning of the reversed list) should point to the
• To do this, utilize a trick:
  • lp.next.next = itr
    • The beginning of the reversed list (and thereby the end) should point to the right partition (itr or future)
  • lp.next = prev
    • The end of the reversed list (and thereby beginning) should now be pointed to by the lp variable.
    • Also notice that we used a dummy variable, which guarantees that even when left starts at the beginning (node 1), we still return dummy.next which will point to the correct beginning (now the end).

Complexity

Runtime

$O(N)$, where N is the amount of nodes, and you traverse once through all of them.

Space

$O(1)$

Code

class Solution:
    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        dummy = ListNode(-1)
        dummy.next = head
        lp = dummy
        itr = head
        for _ in range(1, left):
            lp = itr
            itr = itr.next
 
        prev = None
        for _ in range(left, right + 1):
            future = itr.next
            itr.next = prev
            prev = itr
            itr = future
        
        lp.next.next = itr
        lp.next = prev
        return dummy.next

Notes

Cards

START Basic Front: Reverse Linked List II Back: Save the left part that is not reversed, keep in mind left part.next.next can be changed.

END

---

References

• Reverse Linked List II