In this post, we are going to solve the Reverse Linked List II Leetcode Solution problem of Leetcode. This Leetcode problem is done in many programming languages like C++, Java, and Python.
Problem
Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.
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]
Constraints:
- The number of nodes in the list is
n. 1 <= n <= 500-500 <= Node.val <= 5001 <= left <= right <= n
Now, let’s see the leetcode solution of Reverse Linked List II Leetcode Solution.
Reverse Linked List II Leetcode Solution in Python
class Solution:
# @param head, a ListNode
# @param m, an integer
# @param n, an integer
# @return a ListNode
def reverseBetween(self, head, m, n):
if m == n:
return head
dummyNode = ListNode(0)
dummyNode.next = head
pre = dummyNode
for i in range(m - 1):
pre = pre.next
# reverse the [m, n] nodes
reverse = None
cur = pre.next
for i in range(n - m + 1):
next = cur.next
cur.next = reverse
reverse = cur
cur = next
pre.next.next = cur
pre.next = reverse
return dummyNode.nextReverse Linked List II Leetcode Solution in CPP
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int m, int n) {
ListNode *dummy = new ListNode(0), *pre = dummy, *cur;
dummy -> next = head;
for (int i = 0; i < m - 1; i++) {
pre = pre -> next;
}
cur = pre -> next;
for (int i = 0; i < n - m; i++) {
ListNode* temp = pre -> next;
pre -> next = cur -> next;
cur -> next = cur -> next -> next;
pre -> next -> next = temp;
}
return dummy -> next;
}
};Reverse Linked List II Leetcode Solution in Java
public ListNode reverseBetween(ListNode head, int m, int n) {
if(head == null) return null;
ListNode dummy = new ListNode(0); // create a dummy node to mark the head of this list
dummy.next = head;
ListNode pre = dummy; // make a pointer pre as a marker for the node before reversing
for(int i = 0; i<m-1; i++) pre = pre.next;
ListNode start = pre.next; // a pointer to the beginning of a sub-list that will be reversed
ListNode then = start.next; // a pointer to a node that will be reversed
// 1 - 2 -3 - 4 - 5 ; m=2; n =4 ---> pre = 1, start = 2, then = 3
// dummy-> 1 -> 2 -> 3 -> 4 -> 5
for(int i=0; i<n-m; i++)
{
start.next = then.next;
then.next = pre.next;
pre.next = then;
then = start.next;
}
// first reversing : dummy->1 - 3 - 2 - 4 - 5; pre = 1, start = 2, then = 4
// second reversing: dummy->1 - 4 - 3 - 2 - 5; pre = 1, start = 2, then = 5 (finish)
return dummy.next;
}Note: This problem Reverse Linked List II is generated by Leetcode but the solution is provided by Chase2learn This tutorial is only for Educational and Learning purposes.
