Algorithm
Problem Nmae: Reverse Linked List II
problem Link: https://leetcode.com/problems/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 <= 5001 <= 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;
t = head;
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 {
head = front;
}
rear->next = right;
return head;
}
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;
}
Input
head = [1,2,3,4,5], left = 2, right = 4
Output
[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);
l->next = head;
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;
}
};
Input
head = [1,2,3,4,5], left = 2, right = 4
Output
[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;
ListNode start = head;
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;
}
}
Input
head = [5], left = 1, right = 1
Output
[5]
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const reverseBetween = function(head, left, right) {
if(head == null) return head
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
};
Input
head = [5], left = 1, right = 1
Output
[5]
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def reverseBetween(self, head, m, n):
dummy_left, dummy_left.next, i = ListNode(0), head, 1
prev = dummy_left
while head:
latter = head.next
if m == n:
break
if i == m:
head_left, right = prev, head
if i == n:
head_right, left = head.next, head
if m < i <= n:
head.next = prev
prev, head, i = head, latter, i+1
if m != n:
head_left.next, right.next = left, head_right
return dummy_left.next
Input
head = [1,2,3,4,5], left = 2, right = 4
Output
[1,4,3,2,5]
#6 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _092_ReverseLinkedList2
{
public ListNode ReverseBetween(ListNode head, int m, int n)
{
if (m == n) { return head; }
ListNode dummyHead = new ListNode(-1);
dummyHead.next = 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;
}
return dummyHead.next;
}
}
}
Input
head = [1,2,3,4,5], left = 2, right = 4
Output
[1,4,3,2,5]