**source:**https://leetcode.com/problems/reverse-linked-list-ii/**C/C++**

**Solution to LeetCode**problem

**92**.

**Reverse Linked List II**.

## 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*.

## Examples

**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 <= 500`

`1 <= left <= right <= n`

**Follow up:** Could you do it in one pass?

## Solution

We solve this problem this way:

- Decrease by one the
`left`

and`right`

indexes (to make them based`0`

). - If the
`left > 0`

means that the head of the list will remain the same. - Move a
`l`

pointer to the node before the`left`

node. - To reverse, we need to keep track of the current node, the previus node (to point to it), and the next node to keep moving and reversing node by node.
- Place a
`r`

node at the next node to the`left`

index/node. - Point the
`r`

node to the previous node, and move the next one. - Repeat until the
`r`

node is next to the node at the`right`

index.

- Place a
- Point the node before the
`left`

node to the node at the`rigth`

index. - The
`l`

node shoul point next to the current position of`r`

. - If the
`head`

is not the original node, then we pointed to the node at`right`

.

And it is solved in one pass.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int left, int right) {
if (left == right)
return head;
ListNode *newHead = nullptr;
ListNode *l = head;
ListNode *r = head;
left--;
right--;
if (head && left > 0)
newHead = head;
right -= left;
while (l && l->next && --left > 0)
l = l->next;
ListNode* tmp = nullptr;
ListNode *prev = left == - 1 ? l: l->next;
r = prev ? prev->next: nullptr;
while (r && --right >= 0) {
tmp = r->next;
r->next = prev;
prev = r;
r = tmp;
}
if (!newHead)
newHead = prev;
if (left != -1 && l->next) {
tmp = l->next;
tmp->next = r;
l->next = prev;
} else
l->next = r;
return newHead;
}
};