# 92. Reverse Linked List II
Reverse a linked list from position m to n. Do it in one-pass.
Note: 1 ≤ m ≤ n ≤ length of list.
Example:
Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL
# Solution
Approach 1: Iterative Link Reversal.
Approach 2: Recursion.
# Code (Python)
Approach 1:
def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
# iterative
if m >= n or not head or not head.next or m == 0 or n == 0:
return head
dummy = ListNode(0)
dummy.next = head
prev, first = dummy, head
for _ in range(m - 1):
prev, first = prev.next, first.next
second = first.next
for _ in range(n - m):
third = second.next
second.next = first
first = second
second = third
prev.next.next = second
prev.next = first
return dummy.next
Approach 2:
# Code (C++)
Approach 1:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
// Iterative Link Reversal.
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int m, int n) {
ListNode dummyHead(0);
dummyHead.next = head;
ListNode *prev = &dummyHead;
ListNode *curr = head;
for (int i = 1; i < m; ++i)
{
prev = curr;
curr = curr->next;
}
ListNode *next = curr->next;
for (int i = m; i < n; ++i)
{
ListNode *nextNext = next->next;
next->next = curr;
curr = next;
next = nextNext;
}
prev->next->next = next;
prev->next = curr;
return dummyHead.next;
}
};
Approach 2:
// Recursion.
class Solution {
private:
ListNode *left;
bool stop;
void doReverseBetween(ListNode *right, int m, int n) {
if (n == 1)
return;
// Place the left & right pointers to the proper places.
right = right->next;
if (m > 1)
left = left->next;
doReverseBetween(right, m - 1, n - 1);
// Reverse.
if (left == right || right->next == left)
stop = true;
if (!stop)
std::swap(left->val, right->val);
if (left)
left = left->next;
}
public:
ListNode* reverseBetween(ListNode* head, int m, int n) {
left = head;
stop = false;
doReverseBetween(head, m, n);
return head;
}
};