Nos dan una lista enlazada y las posiciones m y n. Necesitamos invertir la lista enlazada de la posición m a la n.
Ejemplos:
Input : 10->20->30->40->50->60->70->NULL
m = 3, n = 6
Output : 10->20->60->50->40->30->70->NULL
Input : 1->2->3->4->5->6->NULL
m = 2, n = 4
Output : 1->4->3->2->5->6->NULL
Para revertir la lista enlazada de la posición m a la n, encontramos las direcciones de la posición inicial y final de la lista enlazada ejecutando un ciclo, y luego desvinculamos esta parte del resto de la lista y luego usamos la función inversa de lista enlazada normal que hemos utilizado anteriormente para invertir la lista enlazada completa, y la usamos para invertir la parte de la lista enlazada que debe invertirse. Después de la inversión, adjuntamos nuevamente la parte invertida a la lista principal.
C++
// C++ program to reverse a linked list
// from position m to position n
#include <bits/stdc++.h>
using namespace std;
// Linked list node
struct Node {
int data;
struct Node* next;
};
// function used to reverse a linked list
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;
}
// function used to reverse a linked list from position m to n
Node* reverseBetween(Node* head, int m, int n)
{
if (m == n)
return head;
// revs and revend is start and end respectively of the
// portion of the linked list which need to be reversed.
// revs_prev is previous of starting position and
// revend_next is next of end of list to be reversed.
Node *revs = NULL, *revs_prev = NULL;
Node *revend = NULL, *revend_next = NULL;
// Find values of above pointers.
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;
// Reverse linked list starting with revs.
revend = reverse(revs);
// If starting position was not head
if (revs_prev)
revs_prev->next = revend;
// If starting position was head
else
head = revend;
revs->next = revend_next;
return head;
}
void print(struct Node* head)
{
while (head != NULL) {
cout<<head->data<<" ";
head = head->next;
}
cout<<endl;
}
// function to add a new node at the
// beginning of the list
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;
}
// Driver code
int main()
{
struct Node* head = NULL;
push(&head, 70);
push(&head, 60);
push(&head, 50);
push(&head, 40);
push(&head, 30);
push(&head, 20);
push(&head, 10);
reverseBetween(head, 3, 6);
print(head);
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
C
// C program to reverse a linked list
// from position m to position n
#include <stdio.h>
#include <stdlib.h>
// Linked list node
typedef struct Node {
int data;
struct Node* next;
} Node;
// function used to reverse a linked list
Node* reverse(Node* head)
{
Node* prev = NULL;
Node* curr = head;
while (curr) {
Node* next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}
// function used to reverse a linked list from position m to n
Node* reverseBetween(Node* head, int m, int n)
{
if (m == n)
return head;
// revs and revend is start and end respectively of the
// portion of the linked list which need to be reversed.
// revs_prev is previous of starting position and
// revend_next is next of end of list to be reversed.
Node *revs = NULL, *revs_prev = NULL;
Node *revend = NULL, *revend_next = NULL;
// Find values of above pointers.
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;
// Reverse linked list starting with revs.
revend = reverse(revs);
// If starting position was not head
if (revs_prev)
revs_prev->next = revend;
// If starting position was head
else
head = revend;
revs->next = revend_next;
return head;
}
void print(Node* head)
{
while (head != NULL) {
printf("%d ", head->data);
head = head->next;
}
printf("\n");
}
// function to add a new node at the beginning of the list
void push(Node** head_ref, int new_data)
{
Node* new_node = (Node*)malloc(sizeof(Node));
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
// Driver code
int main()
{
Node* head = NULL;
push(&head, 70);
push(&head, 60);
push(&head, 50);
push(&head, 40);
push(&head, 30);
push(&head, 20);
push(&head, 10);
reverseBetween(head, 3, 6);
print(head);
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
Java
// Java program to reverse a linked list
// from position m to position n
class LinkedList {
static Node head;
static class Node {
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
/* Function to reverse the linked list */
static Node reverse(Node node)
{
Node prev = null;
Node current = node;
while (current != null) {
Node next = current.next;
current.next = prev;
prev = current;
current = next;
}
node = prev;
return node;
}
// function used to reverse a linked list from position m to n
static Node reverseBetween(Node head, int m, int n)
{
if (m == n)
return head;
// revs and revend is start and end respectively of the
// portion of the linked list which need to be reversed.
// revs_prev is previous of starting position and
// revend_next is next of end of list to be reversed.
Node revs = null, revs_prev = null;
Node revend = null, revend_next = null;
// Find values of above pointers.
int i = 1;
Node curr = head;
while (curr!=null && 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;
// Reverse linked list starting with revs.
revend = reverse(revs);
// If starting position was not head
if (revs_prev!=null)
revs_prev.next = revend;
// If starting position was head
else
head = revend;
revs.next = revend_next;
return head;
}
// prints content of double linked list
void printList(Node node)
{
while (node != null) {
System.out.print(node.data + " ");
node = node.next;
}
}
// Driver Code
public static void main(String[] args)
{
LinkedList list = new LinkedList();
list.head = new Node(10);
list.head.next = new Node(20);
list.head.next.next = new Node(30);
list.head.next.next.next = new Node(40);
list.head.next.next.next.next = new Node(50);
list.head.next.next.next.next.next = new Node(60);
list.head.next.next.next.next.next.next = new Node(70);
reverseBetween(head,3,6);
list.printList(head);
}
}
// This code has been contributed by Abhijeet Kumar(abhijeet19403)
Python3
# Python3 program to reverse a linked list # from position m to position n # Linked list node class Node: def __init__(self, data): self.data = data self.next = None # The standard reverse function used # to reverse a linked list def reverse(head): prev = None curr = head while (curr): next = curr.next curr.next = prev prev = curr curr = next return prev # Function used to reverse a linked list # from position m to n which uses reverse # function def reverseBetween(head, m, n): if (m == n): return head # revs and revend is start and end respectively # of the portion of the linked list which # need to be reversed. revs_prev is previous # of starting position and revend_next is next # of end of list to be reversed. revs = None revs_prev = None revend = None revend_next = None # Find values of above pointers. i = 1 curr = head while (curr and 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 += 1 revend.next = None # Reverse linked list starting with # revs. revend = reverse(revs) # If starting position was not head if (revs_prev): revs_prev.next = revend # If starting position was head else: head = revend revs.next = revend_next return head def prints(head): while (head != None): print(head.data, end = ' ') head = head.next print() # Function to add a new node at the # beginning of the list def push(head_ref, new_data): new_node = Node(new_data) new_node.data = new_data new_node.next = (head_ref) (head_ref) = new_node return head_ref # Driver code if __name__=='__main__': head = None head = push(head, 70) head = push(head, 60) head = push(head, 50) head = push(head, 40) head = push(head, 30) head = push(head, 20) head = push(head, 10) reverseBetween(head, 3, 6) prints(head) # This code is contributed by rutvik_56
C#
// C# program to reverse a linked list
// from position m to position n
using System;
class LinkedList {
static Node head;
public class Node {
public int data;
public Node next;
public Node(int d)
{
data = d;
next = null;
}
}
// function to add a new node at
// the end of the list
public void AddNode(Node node)
{
if (head == null)
head = node;
else {
Node temp = head;
while (temp.next != null) {
temp = temp.next;
}
temp.next = node;
}
}
// function to reverse the list
static public Node reverse(Node head)
{
Node prev = null, current = head, next = null;
while (current != null) {
next = current.next;
current.next = prev;
prev = current;
current = next;
}
return prev;
}
// function used to reverse a linked list from position m to n
public void reverseBetween( int m, int n)
{
if (m == n)
return ;
// revs and revend is start and end respectively of the
// portion of the linked list which need to be reversed.
// revs_prev is previous of starting position and
// revend_next is next of end of list to be reversed.
Node revs = null, revs_prev = null;
Node revend = null, revend_next = null;
// Find values of above pointers.
int i = 1;
Node curr = head;
while (curr!=null && 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;
// Reverse linked list starting with revs.
revend = reverse(revs);
// If starting position was not head
if (revs_prev!=null)
revs_prev.next = revend;
// If starting position was head
else
head = revend;
revs.next = revend_next;
}
// function to print the list data
public void PrintList()
{
Node current = head;
while (current != null) {
Console.Write(current.data + " ");
current = current.next;
}
Console.WriteLine();
}
}
class GFG{
// Driver Code
public static void Main(string[] args)
{
LinkedList list = new LinkedList();
list.AddNode(new LinkedList.Node(10));
list.AddNode(new LinkedList.Node(20));
list.AddNode(new LinkedList.Node(30));
list.AddNode(new LinkedList.Node(40));
list.AddNode(new LinkedList.Node(50));
list.AddNode(new LinkedList.Node(60));
list.AddNode(new LinkedList.Node(70));
list.reverseBetween(3,6);
list.PrintList();
}
}
// This code is contributed by Abhijeet Kumar(abhijeet19403)
Javascript
<script>
// JavaScript program to reverse a linked list
// from position m to position n
// Linked list node
class Node{
constructor(data){
this.data = data
this.next = null
}
}
// The standard reverse function used
// to reverse a linked list
function reverse(head){
let prev = null
let curr = head
while (curr){
let next = curr.next
curr.next = prev
prev = curr
curr = next
}
return prev
}
// Function used to reverse a linked list
// from position m to n which uses reverse
// function
function reverseBetween(head, m, n){
if (m == n)
return head
// revs and revend is start and end respectively
// of the portion of the linked list which
// need to be reversed. revs_prev is previous
// of starting position and revend_next is next
// of end of list to be reversed.
let revs = null
let revs_prev = null
let revend = null
let revend_next = null
// Find values of above pointers.
let i = 1
let 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 += 1
}
revend.next = null
// Reverse linked list starting with
// revs.
revend = reverse(revs)
// If starting position was not head
if (revs_prev)
revs_prev.next = revend
// If starting position was head
else
head = revend
revs.next = revend_next
return head
}
function prints(head){
while (head != null){
document.write(head.data,' ')
head = head.next
}
document.write("</br>")
}
// Function to add a new node at the
// beginning of the list
function push(head_ref, new_data){
let new_node = new Node(new_data)
new_node.data = new_data
new_node.next = head_ref
head_ref = new_node
return head_ref
}
// Driver code
let head = null
head = push(head, 70)
head = push(head, 60)
head = push(head, 50)
head = push(head, 40)
head = push(head, 30)
head = push(head, 20)
head = push(head, 10)
reverseBetween(head, 3, 6)
prints(head)
// This code is contributed by shinjanpatra
</script>
Producción
10 20 60 50 40 30 70
Complejidad de tiempo: O (N), aquí N es el número de Nodes en la lista enlazada. En el peor de los casos, necesitamos recorrer la lista dos veces.
Espacio Auxiliar: O(1), Como espacio extra constante se utiliza.
Método 2: (recorrido simple)
En este método necesitamos recorrer la lista solo una vez en el peor de los casos. El algoritmo hace uso de la idea de invertir una lista enlazada normal. A continuación se muestra el algoritmo:
- Obtenga el puntero a la cabeza y la cola de la lista enlazada invertida.
- Obtener el puntero al Node anterior al Node mth y al Node posterior al Node nth.
- Invierta la lista como se discutió en esta publicación.
- Vuelva a conectar los enlaces correctamente.
Implementación del enfoque anterior:
C++
// C++ program to reverse a linked list
// from position m to position n
#include <bits/stdc++.h>
using namespace std;
// Linked list node
struct Node {
int data;
struct Node* next;
};
// function used to reverse a linked list from position m to
// n
Node* reverseBetween(Node* head, int m, int n)
{
// First move the current pointer to the node from where
// we have to reverse the linked list
Node *curr = head, *prev = NULL;
// prev points to the node before mth node
int i;
for (i = 1; i < m; i++) {
prev = curr;
curr = curr->next;
}
// This pointer stores the pointer to the head of the
// reversed linkedlist
Node* rtail = curr;
// This pointer stores the pointer to the tail of the
// reversed linkedlist
Node* rhead = NULL;
// Now reverse the linked list from m to n nodes
while (i <= n) {
Node* next = curr->next;
curr->next = rhead;
rhead = curr;
curr = next;
i++;
}
// if prev is not null it means that some of the nodes
// exits before m or we can say m!=1
if (prev != NULL)
prev->next = rhead;
else
head = rhead;
// at this point curr will point to the next of nth
// node where we will connect the tail of the reversed
// linked list
rtail->next = curr;
// at the end return the new head.
return head;
}
void print(struct Node* head)
{
while (head != NULL) {
cout << head->data << " ";
head = head->next;
}
cout << endl;
}
// function to add a new node at the
// beginning of the list
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;
}
// Driver code
int main()
{
struct Node* head = NULL;
push(&head, 70);
push(&head, 60);
push(&head, 50);
push(&head, 40);
push(&head, 30);
push(&head, 20);
push(&head, 10);
struct Node* nhead = reverseBetween(head, 3, 6);
print(nhead);
return 0;
}
// This code is contributed by Abhijeet Kumar(abhijeet19403)
Java
// Java program to reverse a linked list
// from position m to position n
class LinkedList {
static Node head;
static class Node {
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
// function used to reverse a linked list from position
// m to n
static Node reverseBetween(Node head, int m, int n)
{
// First move the current pointer to the node from
// where we have to reverse the linked list
Node curr = head, prev = null;
// prev points to the node before mth node
int i;
for (i = 1; i < m; i++) {
prev = curr;
curr = curr.next;
}
// This pointer stores the pointer to the head of
// the reversed linkedlist
Node rtail = curr;
// This pointer stores the pointer to the tail of
// the reversed linkedlist
Node rhead = null;
// Now reverse the linked list from m to n nodes
while (i <= n) {
Node next = curr.next;
curr.next = rhead;
rhead = curr;
curr = next;
i++;
}
// if prev is not null it means that some of the
// nodes exits before m ( or if m!=1)
if (prev != null)
prev.next = rhead;
else
head = rhead;
// at this point curr will point to the next of nth
// node where we will connect the tail of the
// reversed linked list
rtail.next = curr;
// at the end return the new head.
return head;
}
// prints content of double linked list
void printList(Node node)
{
while (node != null) {
System.out.print(node.data + " ");
node = node.next;
}
}
// Driver Code
public static void main(String[] args)
{
LinkedList list = new LinkedList();
list.head = new Node(10);
list.head.next = new Node(20);
list.head.next.next = new Node(30);
list.head.next.next.next = new Node(40);
list.head.next.next.next.next = new Node(50);
list.head.next.next.next.next.next = new Node(60);
list.head.next.next.next.next.next.next
= new Node(70);
reverseBetween(head, 3, 6);
list.printList(head);
}
}
// This code has been contributed by Abhijeet Kumar(abhijeet19403)
Python3
# Python3 program to reverse a linked list # from position m to position n # Linked list node class Node: def __init__(self, data): self.data = data self.next = None def reverse(head): prev = None curr = head while (curr): next = curr.next curr.next = prev prev = curr curr = next return prev # Function used to reverse a linked list # from position m to n def reverseBetween(head, m, n): # First move the current pointer to the node from # where we have to reverse the linked list curr = head prev = None # prev points to the node before mth node i = 1 while i<m: prev = curr curr = curr.next i+=1 # This pointer stores the pointer to the head of # the reversed linkedlist rtail = curr # This pointer stores the pointer to the tail of # the reversed linkedlist rhead = None # Now reverse the linked list from m to n nodes while (i <= n): temp = curr.next curr.next = rhead rhead = curr curr = temp i+=1 # if prev is not null it means that some of the # nodes exits before m ( or if m!=1) if prev: prev.next = rhead else: head = rhead # at this point curr will point to the next of nth # node where we will connect the tail of the # reversed linked list rtail.next = curr # at the end return the new head. return head def prints(head): while (head != None): print(head.data, end = ' ') head = head.next print() # Function to add a new node at the # beginning of the list def push(head_ref, new_data): new_node = Node(new_data) new_node.data = new_data new_node.next = (head_ref) (head_ref) = new_node return head_ref # Driver code if __name__=='__main__': head = None head = push(head, 70) head = push(head, 60) head = push(head, 50) head = push(head, 40) head = push(head, 30) head = push(head, 20) head = push(head, 10) reverseBetween(head, 3, 6) prints(head) # This code is contributed by Abhijeet Kumar(abhijeet19403)
C#
// C# program to reverse a linked list
// from position m to position n
using System;
class LinkedList {
static Node head;
public class Node {
public int data;
public Node next;
public Node(int d)
{
data = d;
next = null;
}
}
// function to add a new node at
// the end of the list
public void AddNode(Node node)
{
if (head == null)
head = node;
else {
Node temp = head;
while (temp.next != null) {
temp = temp.next;
}
temp.next = node;
}
}
// function used to reverse a linked list from position m to n
public void reverseBetween(int m, int n)
{
// First move the current pointer to the node from
// where we have to reverse the linked list
Node curr = head, prev = null;
// prev points to the node before mth node
int i;
for (i = 1; i < m; i++) {
prev = curr;
curr = curr.next;
}
// This pointer stores the pointer to the head of
// the reversed linkedlist
Node rtail = curr;
// This pointer stores the pointer to the tail of
// the reversed linkedlist
Node rhead = null;
// Now reverse the linked list from m to n nodes
while (i <= n) {
Node next = curr.next;
curr.next = rhead;
rhead = curr;
curr = next;
i++;
}
// if prev is not null it means that some of the
// nodes exits before m ( or if m!=1)
if (prev != null)
prev.next = rhead;
else
head = rhead;
// at this point curr will point to the next of nth
// node where we will connect the tail of the
// reversed linked list
rtail.next = curr;
}
// function to print the list data
public void PrintList()
{
Node current = head;
while (current != null) {
Console.Write(current.data + " ");
current = current.next;
}
Console.WriteLine();
}
}
class GFG{
// Driver Code
public static void Main(string[] args)
{
LinkedList list = new LinkedList();
list.AddNode(new LinkedList.Node(10));
list.AddNode(new LinkedList.Node(20));
list.AddNode(new LinkedList.Node(30));
list.AddNode(new LinkedList.Node(40));
list.AddNode(new LinkedList.Node(50));
list.AddNode(new LinkedList.Node(60));
list.AddNode(new LinkedList.Node(70));
list.reverseBetween(3,6);
list.PrintList();
}
}
// This code is contributed by Abhijeet Kumar(abhijeet19403)
Javascript
<script>
// JavaScript program to reverse a linked list
// from position m to position n
// Linked list node
class Node{
constructor(data){
this.data = data
this.next = null
}
}
// Function used to reverse a linked list
// from position m to n
function reverseBetween(head, m, n){
// First move the current pointer to the node from
// where we have to reverse the linked list
let curr = head;
let prev = null;
// prev points to the node before mth node
let i;
for (i = 1; i < m; i++) {
prev = curr;
curr = curr.next;
}
// This pointer stores the pointer to the head of
// the reversed linkedlist
let rtail = curr;
// This pointer stores the pointer to the tail of
// the reversed linkedlist
let rhead = null;
// Now reverse the linked list from m to n nodes
while (i <= n) {
Node next = curr.next;
curr.next = rhead;
rhead = curr;
curr = next;
i++;
}
// if prev is not null it means that some of the
// nodes exits before m ( or if m!=1)
if (prev != null)
prev.next = rhead;
else
head = rhead;
// at this point curr will point to the next of nth
// node where we will connect the tail of the
// reversed linked list
rtail.next = curr;
}
function prints(head){
while (head != null){
document.write(head.data,' ')
head = head.next
}
document.write("</br>")
}
// Function to add a new node at the
// beginning of the list
function push(head_ref, new_data){
let new_node = new Node(new_data)
new_node.data = new_data
new_node.next = head_ref
head_ref = new_node
return head_ref
}
// Driver code
let head = null
head = push(head, 70)
head = push(head, 60)
head = push(head, 50)
head = push(head, 40)
head = push(head, 30)
head = push(head, 20)
head = push(head, 10)
reverseBetween(head, 3, 6)
prints(head)
// This code is contributed by Abhijeet Kumar(abhijeet19403)
</script>
Producción
10 20 60 50 40 30 70
Complejidad de tiempo: O (n), aquí n es la posición n hasta la cual tenemos que invertir la lista enlazada. En el peor de los casos, necesitamos recorrer la lista una vez cuando n es igual al tamaño de la lista enlazada y, en el mejor de los casos, la complejidad del tiempo puede llegar a O(1).
Espacio Auxiliar: O(1), Como espacio extra constante se utiliza.
Este artículo es una contribución de Akshit Agarwal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA