Reverse Linked List II

Problem Summary

(Write in your own words, not copied from LeetCode. This forces comprehension.)

• Given a linked list, reverse list from left to right
• Return head

Key Observations

(Patterns, constraints, or hints in the problem statement.)

• Use a Dummy Node
• Use Two Pointers

Main Concepts Used

(Mark the CS concepts or algorithms used.)

• Linked List

Time & Space Complexity

• Time: $O(n)$ → Reason: Iterating through the list once
• Space: $O(1)$ → Reason: Not storing the full list

Code

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseBetween(
        self, head: Optional[ListNode], left: int, right: int
    ) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        prev, cur = dummy, head

        i = 1
        while i < left:
            prev, cur = cur, cur.next
            i += 1

        startingsPrev = prev
        starting = cur
        while i <= right:
            next = cur.next
            cur.next = prev
            prev, cur = cur, next
            i += 1

        starting.next = cur
        startingsPrev.next = prev
        return dummy.next

Common Mistakes / Things I Got Stuck On

• Not using a dummy node