Dada una lista enlazada con n Nodes, inviértala de la siguiente manera:
- Si n es par, inviértalo en un grupo de n/2 Nodes.
- Si n es impar, mantenga el Node medio como está, invierta los primeros n/2 elementos e invierta los últimos n/2 elementos.
Ejemplos:
Entrada: 1 2 3 4 5 6 (n es par)
Salida: 3 2 1 6 5 4
Entrada: 1 2 3 4 5 6 7 (n es impar)
Salida: 3 2 1 4 7 6 5
Enfoque: La idea es similar a Invertir una lista enlazada en grupos de tamaño k donde k es n/2. Solo necesita verificar el Node medio.
- Si n es par, divida la lista enlazada en dos partes, es decir, los primeros n/2 elementos y los últimos n/2 elementos e invierta ambas partes.
- Si n es impar, divida la lista enlazada en tres partes, es decir, los primeros n/2 elementos, (n/2 + 1) el elemento th y los últimos n/2 elementos e invierta ambas partes excepto (n/2 + 1) el elemento th.
C++
// C++ program to reverse given
// linked list according to its size
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node* next;
};
// Function to create a new Node
Node* newNode(int data)
{
Node *temp = new Node;
temp->data = data;
temp->next = NULL;
return temp;
}
// Prints a list.
void printList(Node* head)
{
Node *temp = head;
while (temp) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
/* Function to push a Node */
void push(Node** head_ref, int new_data)
{
Node* new_Node = new Node;
new_Node->data = new_data;
new_Node->next = (*head_ref);
(*head_ref) = new_Node;
}
// Returns size of list.
int getSize(Node* head)
{
Node* curr = head;
int count = 0;
while (curr) {
curr = curr->next;
count++;
}
return count;
}
// Function to reverse the linked
// list according to its size
Node* reverseSizeBy2Util(Node* head, int k,
bool skipMiddle)
{
if (!head)
return NULL;
int count = 0;
Node* curr = head;
Node* prev = NULL;
Node* next;
// Reverse current block of list.
while (curr && count < k) {
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
count++;
}
// If size is even, reverse next block too.
if (!skipMiddle)
head->next = reverseSizeBy2Util(next, k, false);
else {
// if size is odd, skip next element
// and reverse the block after that.
head->next = next;
if (next)
next->next = reverseSizeBy2Util(next->next,
k, true);
}
return prev;
}
Node* reverseBySizeBy2(Node* head)
{
// Get the size of list.
int n = getSize(head);
// If the size is even, no need
// to skip middle Node.
if (n % 2 == 0)
return reverseSizeBy2Util(head, n/2, false);
// If size is odd, middle Node has
// to be skipped.
else
return reverseSizeBy2Util(head, n/2, true);
}
// Drivers code
int main()
{
/* Start with the empty list */
Node* head = NULL;
/* Created Linked list is 1->2->3->4->5->6->7->8->9 */
push(&head, 9);
push(&head, 8);
push(&head, 7);
push(&head, 6);
push(&head, 5);
push(&head, 4);
push(&head, 3);
push(&head, 2);
push(&head, 1);
cout << "Original List : ";
printList(head);
cout << "Reversed List : ";
Node* reversedHead = reverseBySizeBy2(head);
printList(reversedHead);
return 0;
}
Java
// Java program to reverse given
// linked list according to its size
class GFG
{
static class Node
{
int data;
Node next;
};
// Function to create a new Node
static Node newNode(int data)
{
Node temp = new Node();
temp.data = data;
temp.next = null;
return temp;
}
// Prints a list.
static void printList(Node head)
{
Node temp = head;
while (temp != null)
{
System.out.print( temp.data + " ");
temp = temp.next;
} System.out.println();
}
// Function to push a Node
static Node push(Node head_ref, int new_data)
{
Node new_Node = new Node();
new_Node.data = new_data;
new_Node.next = (head_ref);
(head_ref) = new_Node;
return head_ref;
}
// Returns size of list.
static int getSize(Node head)
{
Node curr = head;
int count = 0;
while (curr != null)
{
curr = curr.next;
count++;
}
return count;
}
// Function to reverse the linked
// list according to its size
static Node reverseSizeBy2Util(Node head, int k,
boolean skipMiddle)
{
if (head == null)
return null;
int count = 0;
Node curr = head;
Node prev = null;
Node next=null;
// Reverse current block of list.
while (curr!=null && count < k)
{
next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
count++;
}
// If size is even, reverse next block too.
if (!skipMiddle)
head.next = reverseSizeBy2Util(next, k, false);
else
{
// if size is odd, skip next element
// and reverse the block after that.
head.next = next;
if (next != null)
next.next = reverseSizeBy2Util(next.next,
k, true);
}
return prev;
}
static Node reverseBySizeBy2(Node head)
{
// Get the size of list.
int n = getSize(head);
// If the size is even, no need
// to skip middle Node.
if (n % 2 == 0)
return reverseSizeBy2Util(head, n/2, false);
// If size is odd, middle Node has
// to be skipped.
else
return reverseSizeBy2Util(head, n/2, true);
}
// Driver code
public static void main(String args[])
{
// Start with the empty list /
Node head = null;
// Created Linked list is 1.2.3.4.5.6.7.8.9 /
head = push(head, 9);
head = push(head, 8);
head = push(head, 7);
head = push(head, 6);
head = push(head, 5);
head = push(head, 4);
head = push(head, 3);
head = push(head, 2);
head = push(head, 1);
System.out.print( "Original List : ");
printList(head);
System.out.print( "Reversed List : ");
Node reversedHead = reverseBySizeBy2(head);
printList(reversedHead);
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 program to reverse given
# linked list according to its size
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Prints a list.
def printList(head):
temp = head
while temp:
print(temp.data, end = " ")
temp = temp.next
print()
# Function to push a Node
def push(head_ref, new_data):
new_Node = Node(new_data)
new_Node.next = head_ref
head_ref = new_Node
return head_ref
# Returns size of list.
def getSize(head):
curr = head
count = 0
while curr:
curr = curr.next
count += 1
return count
# Function to reverse the linked
# list according to its size
def reverseSizeBy2Util(head, k, skipMiddle):
if not head:
return None
count = 0
curr, prev, next = head, None, None
# Reverse current block of list.
while curr and count < k:
next = curr.next
curr.next = prev
prev = curr
curr = next
count += 1
# If size is even, reverse next block too.
if not skipMiddle:
head.next = reverseSizeBy2Util(next, k, False)
else:
# if size is odd, skip next element
# and reverse the block after that.
head.next = next
if next:
next.next = reverseSizeBy2Util(next.next,
k, True)
return prev
def reverseBySizeBy2(head):
# Get the size of list.
n = getSize(head)
# If the size is even, no
# need to skip middle Node.
if n % 2 == 0:
return reverseSizeBy2Util(head, n//2, False)
# If size is odd, middle
# Node has to be skipped.
else:
return reverseSizeBy2Util(head, n//2, True)
# Drivers code
if __name__ == "__main__":
# Start with the empty list
head = None
# Created Linked list is 1.2.3.4.5.6.7.8.9
head = push(head, 9)
head = push(head, 8)
head = push(head, 7)
head = push(head, 6)
head = push(head, 5)
head = push(head, 4)
head = push(head, 3)
head = push(head, 2)
head = push(head, 1)
print("Original List : ", end = "")
printList(head)
print("Reversed List : ", end = "")
reversedHead = reverseBySizeBy2(head)
printList(reversedHead)
# This code is contributed by Rituraj Jain
C#
// C# program to reverse given
// linked list according to its size
using System;
class GFG
{
public class Node
{
public int data;
public Node next;
};
// Function to create a new Node
static Node newNode(int data)
{
Node temp = new Node();
temp.data = data;
temp.next = null;
return temp;
}
// Prints a list.
static void printList(Node head)
{
Node temp = head;
while (temp != null)
{
Console.Write( temp.data + " ");
temp = temp.next;
} Console.WriteLine();
}
// Function to push a Node
static Node push(Node head_ref, int new_data)
{
Node new_Node = new Node();
new_Node.data = new_data;
new_Node.next = (head_ref);
(head_ref) = new_Node;
return head_ref;
}
// Returns size of list.
static int getSize(Node head)
{
Node curr = head;
int count = 0;
while (curr != null)
{
curr = curr.next;
count++;
}
return count;
}
// Function to reverse the linked
// list according to its size
static Node reverseSizeBy2Util(Node head, int k,
Boolean skipMiddle)
{
if (head == null)
return null;
int count = 0;
Node curr = head;
Node prev = null;
Node next=null;
// Reverse current block of list.
while (curr!=null && count < k)
{
next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
count++;
}
// If size is even, reverse next block too.
if (!skipMiddle)
head.next = reverseSizeBy2Util(next, k, false);
else
{
// if size is odd, skip next element
// and reverse the block after that.
head.next = next;
if (next != null)
next.next = reverseSizeBy2Util(next.next,
k, true);
}
return prev;
}
static Node reverseBySizeBy2(Node head)
{
// Get the size of list.
int n = getSize(head);
// If the size is even, no need
// to skip middle Node.
if (n % 2 == 0)
return reverseSizeBy2Util(head, n/2, false);
// If size is odd, middle Node has
// to be skipped.
else
return reverseSizeBy2Util(head, n/2, true);
}
// Driver code
public static void Main(String []args)
{
// Start with the empty list /
Node head = null;
// Created Linked list is 1.2.3.4.5.6.7.8.9 /
head = push(head, 9);
head = push(head, 8);
head = push(head, 7);
head = push(head, 6);
head = push(head, 5);
head = push(head, 4);
head = push(head, 3);
head = push(head, 2);
head = push(head, 1);
Console.Write( "Original List : ");
printList(head);
Console.Write( "Reversed List : ");
Node reversedHead = reverseBySizeBy2(head);
printList(reversedHead);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript program to reverse given
// linked list according to its size
class Node {
constructor() {
this.data = 0;
this.next = null;
}
}
// Function to create a new Node
function newNode(data) {
var temp = new Node();
temp.data = data;
temp.next = null;
return temp;
}
// Prints a list.
function printList(head) {
var temp = head;
while (temp != null) {
document.write(temp.data + " ");
temp = temp.next;
}
document.write("<br>");
}
// Function to push a Node
function push(head_ref, new_data) {
var new_Node = new Node();
new_Node.data = new_data;
new_Node.next = head_ref;
head_ref = new_Node;
return head_ref;
}
// Returns size of list.
function getSize(head) {
var curr = head;
var count = 0;
while (curr != null) {
curr = curr.next;
count++;
}
return count;
}
// Function to reverse the linked
// list according to its size
function reverseSizeBy2Util(head, k, skipMiddle) {
if (head == null) return null;
var count = 0;
var curr = head;
var prev = null;
var next = null;
// Reverse current block of list.
while (curr != null && count < k) {
next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
count++;
}
// If size is even, reverse next block too.
if (!skipMiddle) head.next =
reverseSizeBy2Util(next, k, false);
else {
// if size is odd, skip next element
// and reverse the block after that.
head.next = next;
if (next != null) next.next =
reverseSizeBy2Util(next.next, k, true);
}
return prev;
}
function reverseBySizeBy2(head) {
// Get the size of list.
var n = getSize(head);
// If the size is even, no need
// to skip middle Node.
if (n % 2 == 0)
return reverseSizeBy2Util(head, parseInt(n / 2), false);
// If size is odd, middle Node has
// to be skipped.
else
return reverseSizeBy2Util(head, parseInt(n / 2), true);
}
// Driver code
// Start with the empty list /
var head = null;
// Created Linked list is 1.2.3.4.5.6.7.8.9 /
head = push(head, 9);
head = push(head, 8);
head = push(head, 7);
head = push(head, 6);
head = push(head, 5);
head = push(head, 4);
head = push(head, 3);
head = push(head, 2);
head = push(head, 1);
document.write("Original List : ");
printList(head);
document.write("Reversed List : ");
var reversedHead = reverseBySizeBy2(head);
printList(reversedHead);
</script>
Producción:
Original List : 1 2 3 4 5 6 7 8 9 Reversed List : 4 3 2 1 5 9 8 7 6
Publicación traducida automáticamente
Artículo escrito por Aashish Chauhan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA