1. Introduction
The problem titled "Leetcode 92 Reverse Linked List II" is a coding problem that involves reversing a portion of a linked list. In this article, we will discuss the problem statement, explain the approach to solve it, and provide a Python implementation.
2. Problem Statement
The problem requires us to reverse a linked list from position m to n. We are given the head of the linked list as input, which is a reference to the first node, and two integers m and n. The position m and n are 1-indexed, with 1 representing the first node of the linked list.
Example
Consider the following linked list: 1 -> 2 -> 3 -> 4 -> 5. If m is 2 and n is 4, then the resulting linked list after reversing from position 2 to 4 would be 1 -> 4 -> 3 -> 2 -> 5.
3. Approach
To solve this problem, we will use a three-pointer approach. We will maintain three pointers: prev, curr, and next. The prev pointer is used to store the node before the m-th position, the curr pointer is used to track the current node, and the next pointer is used to store the next node after the current node.
We will start by traversing the linked list until we reach the m-th position. At this point, we will save the current node in the prev pointer. Then, we will keep reversing the linked list by moving the curr pointer to the next node and updating the next node to point to the previous node. This process will continue until we reach the n-th position.
After the reversal, we need to reconnect the reversed portion with the rest of the linked list. To do this, we will connect the node at position m-1 with the reversed portion and connect the node at position n+1 with the remaining portion after the reversed portion.
Algorithm
Initialize prev, curr and next pointers to None.
Traverse the linked list until the m-th position.
Save the current node in the prev pointer and move the curr pointer to the next node.
Reverse the linked list from position m to n by updating the next pointers.
Connect the reversed portion with the rest of the linked list.
Return the updated head node of the linked list.
4. Python Implementation
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverseBetween(head: ListNode, m: int, n: int) -> ListNode:
if not head or m == n:
return head
dummy = ListNode(-1)
dummy.next = head
prev = dummy
for _ in range(m - 1):
prev = prev.next
curr = prev.next
for _ in range(n - m):
next_node = curr.next
curr.next = next_node.next
next_node.next = prev.next
prev.next = next_node
return dummy.next
# Example usage
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)
m = 2
n = 4
new_head = reverseBetween(head, m, n)
while new_head:
print(new_head.val, end=" ")
new_head = new_head.next
# Output: 1 4 3 2 5
5. Complexity Analysis
The time complexity of this approach is O(n), where n is the number of nodes in the linked list. This is because we only need to traverse the linked list once.
The space complexity of this approach is O(1) since no extra space is required apart from a few pointers.
6. Conclusion
In this article, we discussed the problem "Leetcode 92 Reverse Linked List II" and provided a detailed approach to solve it. We explained the underlying algorithm and provided a Python implementation. Understanding linked list manipulations is important for solving a variety of programming problems and this article provides a valuable insight into one such problem.