A LeetCode Daily Series — Day 87

Today’s problem is called "Reverse Linked List II"

Updated: at 02:06 AM

In this article, we’ll dive into the problem of reversing a subsection of a singly linked list, specifically between two given positions. We’ll explore the problem, understand a naive approach, and then delve into more efficient solutions to tackle the task. By the end of this read, you’ll be equipped with multiple ways to solve this problem effectively.

If you’re just joining us, it might be helpful to catch up on the previous entries. Want to see more problem-solving techniques? Follow me here on my blog!

Cover Image

Understanding the Problem

Given the head of a singly linked list and two integers left and right where left < = right, our task is to reverse the nodes of the list from position left to position right, and return the modified list.

Example 1:

Example 1

Input: head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]

Example 2:

Input: head = [5], left = 1, right = 1
Output: [5]

Using Efficient Approach 1: Pointer Manipulation

One efficient approach to solve this problem involves using pointer manipulation to reverse the nodes within the specified range. This method involves three main steps: reaching the left position, reversing the nodes between left and right, and updating the pointers to reflect the changes.

def reverseBetween(
    self, head: Optional[ListNode], left: int, right: int
) -> Optional[ListNode]:
    dummy = ListNode(0, head)

    # 1) reach node at position "left"
    leftPrev, cur = dummy, head
    for i in range(left - 1):
        leftPrev, cur = cur, cur.next

    # Now cur="left", leftPrev="node before left"
    # 2) reverse from left to right
    prev = None
    for i in range(right - left + 1):
        tmpNext = cur.next
        cur.next = prev
        prev, cur = cur, tmpNext

    # 3) Update pointers
    leftPrev.next.next = cur  # cur is node after "right"
    leftPrev.next = prev  # prev is "right"
    return dummy.next

Explanation

  1. Initialization:

    • We use a dummy node to simplify edge cases where the reversal starts at the head. The dummy node points to the head of the list.
    • We set leftPrev to the dummy and cur to the head.
    • We then traverse the list until cur is at the left position, updating leftPrev to the node just before left.

  2. Reversal:

    • We reverse the links between the nodes from left to right. We use a prev pointer initialized to None and update it to point to the current node (cur) while advancing cur to the next node (tmpNext).
    • We repeat this process right - left + 1 times, effectively reversing the section.

  3. Update Pointers:

    • After reversing, cur points to the node after right and prev points to the node at right.
    • We update the next pointer of the node just before left (leftPrev.next.next) to point to cur.
    • We also update leftPrev.next to point to prev, completing the reattachment of the reversed section back to the list.

Time Complexity: O(n), where n is the number of nodes in the list. We traverse the list a constant number of times.

Space Complexity: O(1), as we only use a few extra pointers.

PM Results

Conclusion

Reversing a subsection of a linked list can be efficiently solved using pointer manipulation techniques. We explored an efficient method that achieves this with optimal time and space complexity.

Understanding these methods enhances your problem-solving skills and prepares you for tackling similar challenges in coding interviews and competitions.

Found this helpful? Follow me for more leetcode adventures! Questions? React out via email.

Next Articles in the Series