Reverse Linked List II Leetcode Problem 92 [Python Solution]

Welcome back to another coding tutorial!

In this post, we’ll tackle the LeetCode problem #92, “Reverse Linked List II,” which falls under the category of linked list problems.

We’ll provide a Python solution to this problem and walk you through the entire process step by step.

By the end of this tutorial, you’ll have a clear understanding of how to reverse a portion of a linked list.

If you’re new to coding or looking to improve your skills, this guide is designed to help beginners.

We’ll break down the problem, explain the constraints, and provide both a brute-force approach and an efficient solution, so you can choose the one that suits your needs.

Before we dive into the solution, let’s start by understanding the problem and its constraints.

Problem Overview

You’re given the head of a singly linked list, two integers left and right, where left is less than or equal to right.

Your task is to reverse the nodes of the linked list from position left to position right and return the reversed list.

Let’s illustrate this with an example:

Example 1:

Input:

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

Output:

[1,4,3,2,5]

In this example, we need to reverse the nodes between positions 2 and 4 in the linked list.

Constraints

Before we proceed with the solution, it’s essential to understand the constraints of the problem:

• The number of nodes in the list is n.
• 1 <= n <= 500
• -500 <= Node.val <= 500
• 1 <= left <= right <= n

Now that we have a clear picture of the problem, let’s explore our Python solution.

Efficient Python Code Solution

We’ll provide a Python solution that follows a simple and efficient approach to reverse the linked list.

To make the implementation easier and handle edge cases more smoothly, we’ll use a dummy node.

The dummy node is a fake node that simplifies various aspects of linked list manipulation.

class Solution:
    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        # Create a dummy node and set its next pointer to the head
        dummy = ListNode(0, head)

        # Phase 1: Reach the left position
        leftPrev, cur = dummy, head
        for i in range(left - 1):
            leftPrev, cur = cur, cur.next

        # Phase 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

        # Phase 3: Update pointers
        leftPrev.next.next = cur  # cur is the node after "right"
        leftPrev.next = prev  # prev is "right"

        return dummy.next

Let’s break down the solution into phases and understand the code step by step.

Phase 1: Reach the Left Position

In this phase, we aim to position our pointers at the left node and the node right before it.

We use two pointers, leftPrev and cur.

The leftPrev pointer is always one step behind the cur pointer.

• leftPrev points to the node right before the left position.
• cur points to the node at the left position.

We iterate through the linked list left - 1 times to reach the desired positions.

Phase 2: Reverse from Left to Right

In this phase, we reverse the linked list from the left position to the right position.

We use two pointers, prev and cur.

• prev points to the previous node.
• cur points to the current node.

We perform the reversal by breaking the links between nodes and updating the pointers.

This process is repeated right - left + 1 times, which covers the specified range.

Phase 3: Update Pointers

After the reversal, we need to adjust the pointers to connect the reversed portion back to the main linked list.

• We set leftPrev.next.next to cur, which is the node after the right position.
• We update leftPrev.next to point to prev, which is the right node.

At this point, the linked list is correctly modified, and we can return the head of the list.

By using a dummy node and breaking the problem into phases, we’ve made the implementation cleaner and more manageable.

Time and Space Complexity

Let’s analyze the time and space complexity of our solution.

Time Complexity:

Our solution has a time complexity of O(n), where ‘n’ is the number of nodes in the linked list.

This is because we traverse the entire list once to reach the left position, then reverse the nodes from left to right, and finally update the pointers.

Space Complexity:

The space complexity is O(1) because we use a constant amount of additional space regardless of the input size.

We don’t create any data structures that depend on the size of the linked list.

Reasoning Behind Our Approach

Our approach is efficient and follows a simple three-phase process.

Here’s the reasoning behind each phase:

Phase 1: Reach the Left Position

To reverse a portion of the linked list, we must first reach the left position.

We use the leftPrev pointer to point to the node right before left and the cur pointer to point to the left node.

This positioning is crucial for later phases.

Phase 2: Reverse from Left to Right

Reversing a portion of the linked list involves breaking and reassigning the links between nodes.

This phase focuses on reversing the nodes from left to right.

By maintaining two pointers, prev and cur, we can efficiently reverse the linked list.

Phase 3: Update Pointers

After the reversal, we need to reconnect the reversed portion to the main linked list.

This involves updating the pointers.

The leftPrev.next.next is set to cur, which is the node after right. leftPrev.next is updated to prev, which is the right node.

This adjustment ensures that the linked list is correctly modified.

Our approach is efficient and avoids unnecessary complexities.

We use a dummy node to simplify edge cases and offer a straightforward solution to this problem.

Related Interview Questions By Company:

• Remove All Adjacent Duplicates In String II LeetCode
• Graph Valid Tree LeetCode
• Detect Squares LeetCode

Related Interview Questions By Difficulty:

• Merge Two Sorted Lists LeetCode
• Sort List LeetCode
• Intersection Of Two Linked Lists LeetCode

Related Interview Questions By Category:

• Insertion Sort List LeetCode
• IPO LeetCode
• Partition To K Equal Sum Subsets LeetCode

Conclusion

In this tutorial, we’ve explored the LeetCode problem #92, “Reverse Linked List II,” and provided a Python solution that efficiently reverses a portion of a linked list.

We’ve explained each phase of the solution, highlighted the use of a dummy node, and discussed the time and space complexity.

If you’re a beginner in coding, this guide is designed to help you understand the problem and its solution step by step.

Coding is a skill that improves with practice, so don’t hesitate to try different approaches and explore other problems on platforms like LeetCode to enhance your coding skills.

We encourage you to comment, ask questions,

make suggestions, and share this content with others who might find it helpful.

Learning from one another and engaging in discussions is a great way to grow as a coder.

Question Link: Reverse Linked List II on LeetCode

Thank you for joining us in this coding journey, and we look forward to bringing you more coding tutorials in the future!