Last Updated on March 25, 2022 by Ria Pathak
Concepts Used
Reversing a linked list,pointers
Difficulty Level
Hard.
Problem Statement :
Reverse a linked list from position M to N. Do it in-place and in one-pass.
Example:
Given 1−>2−>3−>4−>5−>NULL, M=1 and N=3, Output: 3−>2−>1−>4−>5−>NULL.
EXPLANATION:
Since we have to reverse a part of the given linked list obviously we need the concept of reversing the linked list. We need to find the mth node and pass it to the reverse function (which will reverse the given part). But, before passing the mth node we need to traverse to the nth node and cut its link with (n+1)th node if present.
Also we have to save the (m-1) node and also (n+1)th node address so that we can link the reversed part of the linked list again with the original linked list.
There will be four variables.
Prev→ for storing the previous node, i.e. (m-1)th node.
Start→ for storing the starting(mth) node of reversal.
End→ for storing the ending node(nth) of reversal.
Next→ for storing the next node, i.e. (n+1)th node.Now, we will pass Start to the reverse function and then will attach the reversed part with Start and End to get the reversed linked list.
SOLUTIONS:
#include <stdio.h>
#include<stdlib.h>
struct Node {
int data;
struct Node* next;
};
struct Node* reverse(struct Node* head)
{
struct Node* prev = NULL;
struct Node* curr = head;
while (curr) {
struct Node* next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}
struct Node* reverseBetween(struct Node* head, int m, int n)
{
if (m == n)
return head;
struct Node* revs = NULL, *revs_prev = NULL;
struct Node* revend = NULL, *revend_next = NULL;
int i = 1;
struct Node* curr = head;
while (curr && i <= n) {
if (i < m)
revs_prev = curr;
if (i == m)
revs = curr;
if (i == n) {
revend = curr;
revend_next = curr->next;
}
curr = curr->next;
i++;
}
revend->next = NULL;
revend = reverse(revs);
if (revs_prev)
revs_prev->next = revend;
else
head = revend;
revs->next = revend_next;
return head;
}
void print(struct Node* head)
{
while (head != NULL) {
printf("%d ", head->data);
head = head->next;
}
printf("\n");
}
void push(struct Node** head_ref, int new_data)
{
struct Node* new_node ;
new_node=(struct Node *)malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
int main()
{ int k;scanf("%d",&k);
int x[k];
for(int i=0;i<k;i++)
scanf("%d",&x[i]);
struct Node* head = NULL;
for(int i=k-1;i>=0;i--)
{
push(&head, x[i]);
}
int m,n;scanf("%d%d",&m,&n);
reverseBetween(head,m,n);
print(head);
return 0;
}
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* next;
};
struct Node* reverse(struct Node* head)
{
struct Node* prev = NULL;
struct Node* curr = head;
while (curr) {
struct Node* next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}
Node* reverseBetween(Node* head, int m, int n)
{
if (m == n)
return head;
Node* revs = NULL, *revs_prev = NULL;
Node* revend = NULL, *revend_next = NULL;
int i = 1;
Node* curr = head;
while (curr && i <= n) {
if (i < m)
revs_prev = curr;
if (i == m)
revs = curr;
if (i == n) {
revend = curr;
revend_next = curr->next;
}
curr = curr->next;
i++;
}
revend->next = NULL;
revend = reverse(revs);
if (revs_prev)
revs_prev->next = revend;
else
head = revend;
revs->next = revend_next;
return head;
}
void print(struct Node* head)
{
while (head != NULL) {
printf("%d ", head->data);
head = head->next;
}
printf("\n");
}
void push(struct Node** head_ref, int new_data)
{
struct Node* new_node = new Node;
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
int main()
{ int k;cin>>k;
int x[k];
for(int i=0;i<k;i++)
cin>>x[i];
struct Node* head = NULL;
for(int i=k-1;i>=0;i--)
{
push(&head, x[i]);
}
int m,n;cin>>m>>n;
reverseBetween(head,m,n);
print(head);
return 0;
}
class Solution {
public:
ListNode *reverseBetween(ListNode *head, int m, int n) {
ListNode* newHead = new ListNode(-1);
newHead->next = head;
ListNode* prev = newHead;
for(auto i = 0 ; i < m-1 ; i++){
prev = prev->next;
}
ListNode* const reversedPrev = prev;
//position m
prev = prev->next;
ListNode* cur = prev->next;
for(auto i = m ; i < n ; i++){
prev->next = cur->next;
cur->next = reversedPrev->next;
reversedPrev->next = cur;
cur = prev->next;
}
return newHead->next;
}
};
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def reverse(self):
prev = None
current = self.head
while(current is not None):
next = current.next
current.next = prev
prev = current
current = next
self.head = prev
def push(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
self.head = new_node
def printList(self):
temp = self.head
while(temp):
print(temp.data, end=" ")
temp = temp.next
llist = LinkedList()
llist.push(20)
llist.push(4)
llist.push(15)
llist.push(85)
print("Given Linked List")
llist.printList()
llist.reverse()
print("\nReversed Linked List")
llist.printList()
[forminator_quiz id="2254"]
This article tried to discuss Reversing a linked list,Pointers. Hope this blog helps you understand and solve the problem. To practice more problems on Reversing a linked list,Pointers you can check out MYCODE | Competitive Programming.