## Algorithm

Problem Nmae: Reverse Linked List II

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 <= 500`
• `1 <= left <= right <= n`

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
#include <stdio.h>
#include <stdlib.h>

struct ListNode {
int val;
struct ListNode *next;
};

struct ListNode *reverseBetween(struct ListNode *head, int m, int n) {
struct ListNode *front, *rear; /* front and rear node of reversed list */
struct ListNode *left, *right; /* left and right linked point */
struct ListNode *p, *q, *t;
front = rear = left = right = NULL;

int len = n - m + 1;
m -= 1;
while (m--) {
left = t;
t = t->next;
}

rear = t;
p = q = NULL;
while (len--) {
q = t->next;
t->next = p;
p = t;
t = q;
}
right = t;
front = p;

/* left to front, rear to right */
if (left) {
left->next = front;
}
else {
}
rear->next = right;

}

int main() {
struct ListNode *l1 = (struct ListNode *)calloc(5, sizeof(struct ListNode));
struct ListNode *p = l1;

int i;
for (i = 1; i <= 4; i++) {
p->val = i;
p->next = p + 1;
p++;
}
p->val = 5;
p->next = NULL;

p = l1;
while (p) {
printf("%d ", p->val);
p = p->next;
}
printf("\n");

p = reverseBetween(l1, 2, 4);
while (p) {
printf("%d ", p->val);
p = p->next;
}
printf("\n");

struct ListNode *l2 = (struct ListNode *)calloc(2, sizeof(struct ListNode));
l2->val = 3;
l2->next = l2 + 1;
l2->next->val = 5;
l2->next->next = NULL;

p = l2;
while (p) {
printf("%d ", p->val);
p = p->next;
}
printf("\n");

p = reverseBetween(l2, 1, 2);
while (p) {
printf("%d ", p->val);
p = p->next;
}
printf("\n");

return 0;
}
``````
Copy The Code &

Input

cmd
head = [1,2,3,4,5], left = 2, right = 4

Output

cmd
[1,4,3,2,5]

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int m, int n) {
ListNode* l = new ListNode(0);
int x = m, y = n - m;
while(--x) l = l->next;
ListNode* pre = l->next, *cur = pre->next, *next;
while(y--){
next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
l->next->next = cur;
l->next = pre;
return m == 1 ? pre : head;
}
};
``````
Copy The Code &

Input

cmd
head = [1,2,3,4,5], left = 2, right = 4

Output

cmd
[1,4,3,2,5]

### #3 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
ListNode prev = null;
for (int i = 1; i < left; i++) {
prev = start;
start = start.next;
}
ListNode end = start;
for (int i = left; i < right; i++) {
end = end.next;
}
ListNode nextToEnd = end.next;
end.next = null;
ListNode reverseStart = reverse(start);
if (prev != null) {
prev.next = reverseStart;
}
ListNode curr = reverseStart;
while (curr.next != null) {
curr = curr.next;
}
curr.next = nextToEnd;
return prev == null ? reverseStart : head;
}

private ListNode reverse(ListNode node) {
ListNode prev = null;
ListNode next = null;
ListNode curr = node;
while (curr != null) {
next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
}
``````
Copy The Code &

Input

cmd
head = [5], left = 1, right = 1

Output

cmd
[5]

### #4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const reverseBetween = function(head, left, right) {
const dummy = new ListNode(null, head)
let num = 0, cur = head
while (cur) {
num++
cur = cur.next
}
let idx = 0, pre = null
cur = dummy
while (idx < right && idx <= num) {
if (idx === left - 1) pre = cur
if (idx >= left) {
const tmp = pre.next
pre.next = cur.next
cur.next = cur.next.next
pre.next.next = tmp
}

if (idx < left) cur = cur.next
idx++
}
return dummy.next
};
``````
Copy The Code &

Input

cmd
head = [5], left = 1, right = 1

Output

cmd
[5]

### #5 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
dummy_left, dummy_left.next, i = ListNode(0), head, 1
prev = dummy_left
if m == n:
break
if i == m:
if i == n:
if m < i <= n:
if m != n:
return dummy_left.next
``````
Copy The Code &

Input

cmd
head = [1,2,3,4,5], left = 2, right = 4

Output

cmd
[1,4,3,2,5]

### #6 Code Example with C# Programming

```Code - C# Programming```

``````
namespace LeetCode
{
{
public ListNode ReverseBetween(ListNode head, int m, int n)
{
if (m == n) { return head; }

ListNode p = dummyHead, q, r;
int i = 0;

for (i = 0; i < m - 1; i++)
{
p = p.next;
}

q = p.next;
for (i = m; i < n; i++)
{
r = q.next;
q.next = r.next;
r.next = p.next;
p.next = r;
}

}
}
}
``````
Copy The Code &

Input

cmd
head = [1,2,3,4,5], left = 2, right = 4

Output

cmd
[1,4,3,2,5]