NUHMAN.com

Introduction

LeetCode 92: Reverse Linked List II asks us to reverse a portion of a singly linked list. Given a linked list, we are provided with two integers m and n, where m is the starting position and n is the ending position of the sublist that should be reversed. We must return the modified linked list after reversing the nodes between positions m and n (1-based indexing).

This problem tests your understanding of linked lists and how to manipulate them efficiently using pointers. The challenge lies in reversing the sublist in-place, meaning that we cannot use extra space to create a new linked list.

Problem Statement

Given a singly linked list and two integers m and n, reverse the linked list from position m to n, and return its head.

Example:

go

Input: head = [1,2,3,4,5], m = 2, n = 4
Output: [1,4,3,2,5]

In this example, we reverse the sublist between nodes 2 and 4. The new list after the reversal is [1, 4, 3, 2, 5].

Approach: In-place Reversal

To solve this problem, we can break it down into the following steps:

1. Edge Case Handling:

• If m equals n, the sublist has only one node and does not require any reversal.
• If the linked list has fewer than m or n nodes, we do not need to perform any reversal.

1. Traverse to the m-th node:

• First, we need to find the node just before the m-th node. This node will help in reconnecting the reversed sublist back to the main list.

1. Reverse the sublist between positions m and n:

• Using the classic linked list reversal technique, we reverse the nodes between positions m and n.

1. Reconnect the reversed sublist:

• Once the sublist is reversed, we reconnect the reversed portion back to the rest of the linked list.

Go Implementation

go

type ListNode struct {
    Val  int
    Next *ListNode
}

func reverseBetween(head *ListNode, m int, n int) *ListNode {
    // Base case: if m == n, no need to reverse
    if m == n {
        return head
    }

    // Create a dummy node to handle edge cases like reversing the first few nodes
    dummy := &ListNode{Next: head}
    prev := dummy
    
    // Move prev to the node just before the m-th node
    for i := 1; i < m; i++ {
        prev = prev.Next
    }
    
    // Initialize pointers for reversing the sublist
    current := prev.Next
    next := current.Next
    
    // Reverse the sublist between m and n
    for i := m; i < n; i++ {
        current.Next = next.Next
        next.Next = prev.Next
        prev.Next = next
        next = current.Next
    }
    
    return dummy.Next
}

Explanation

1. Base Case:

If m == n, no reversal is necessary. The sublist contains only one node, and hence, we return the head of the list as is.

2. Dummy Node:

We create a dummy node that points to the head of the list. This dummy node helps simplify edge cases where the sublist to be reversed starts at the very beginning of the linked list (i.e., m = 1).

3. Find the Node Before the m-th Node:

We traverse the list to reach the node just before the m-th node. This is done using the prev pointer, which starts from the dummy node and moves m-1 steps forward.

4. Reverse the Sublist:

• We initialize the current pointer to point to the m-th node and the next pointer to point to the m+1-th node.
• Using a loop, we reverse the nodes between m and n by adjusting the Next pointers.
• For each iteration, we move the next node into the reversed sublist by modifying the Next pointers of current, prev, and next.

5. Reconnect the Reversed Sublist:

After reversing the nodes, we return dummy.Next, which is the new head of the list.

Time and Space Complexity

MetricComplexityTime ComplexityO(n)Space ComplexityO(1)

Where n is the number of nodes in the linked list:

• The time complexity is O(n) because we traverse the list twice — once to find the m-th node and once to reverse the sublist.
• The space complexity is O(1) since we are modifying the list in place and not using extra space.

Edge Cases

1. Reversing the entire list:

• If m = 1 and n is the length of the list, the entire list should be reversed.
• Example: head = [1, 2, 3, 4, 5], m = 1, n = 5
• Output: [5, 4, 3, 2, 1]

1. Sublist has only one node:

• If m == n, no reversal is needed.
• Example: head = [1, 2, 3], m = 2, n = 2
• Output: [1, 2, 3]

1. Sublist at the beginning:

• If the sublist starts at the head of the list, we handle it with the dummy node to simplify the reversal.
• Example: head = [1, 2, 3, 4, 5], m = 1, n = 3
• Output: [3, 2, 1, 4, 5]

1. Sublist at the end:

• If the sublist ends at the last node, we reverse it correctly while keeping the rest of the list intact.
• Example: head = [1, 2, 3, 4, 5], m = 3, n = 5
• Output: [1, 2, 5, 4, 3]

Conclusion

LeetCode 92: Reverse Linked List II is an excellent exercise in linked list manipulation. By using a dummy node and careful pointer management, we can reverse a portion of the linked list in-place, ensuring that we handle edge cases such as reversing at the beginning or the end of the list.

The O(n) time complexity and O(1) space complexity make this solution efficient even for large linked lists. This problem provides a good understanding of how to manipulate linked lists and is a valuable practice for anyone looking to improve their algorithmic problem-solving skills.