Dada una lista enlazada, invierta los Nodes alternativos y agréguelos al final de la lista. El espacio adicional permitido es O(1)
Ejemplos:
Input: 1->2->3->4->5->6 Output: 1->3->5->6->4->2 Explanation: Two lists are 1->3->5 and 2->4->6, reverse the 2nd list: 6->4->2. Merge the lists Input: 12->14->16->18->20 Output: 12->16->20->18->14 Explanation: Two lists are 12->16->20 and 14->18, reverse the 2nd list: 18->14. Merge the lists
Acercarse:
- La idea es mantener dos listas enlazadas, una lista de todos los Nodes en posiciones impares y otra lista de todos los Nodes en posiciones pares.
- Atraviese la lista enlazada dada, que se considera una lista impar o Nodes colocados de forma extraña.
- Si el Node es un Node par, elimínelo de la lista impar y agréguelo al principio de la lista de Nodes pares. Los Nodes se agregan al frente para mantener el orden inverso.
- Agregue la lista de Nodes pares al final de la lista de Nodes impares.
Ilustración:
Implementación:
C++
// C++ program to reverse alternate
// nodes of a linked list and append
// at the end
#include <bits/stdc++.h>
using namespace std;
/* A linked list node */
class Node {
public:
int data;
Node* next;
};
/* Function to reverse all even positioned
node and append at the end odd is the head
node of given linked list */
void rearrange(Node* odd)
{
// If linked list has less than 3
// nodes, no change is required
if (odd == NULL || odd->next == NULL || odd->next->next == NULL)
return;
// even points to the beginning of even list
Node* even = odd->next;
// Remove the first even node
odd->next = odd->next->next;
// odd points to next node in odd list
odd = odd->next;
// Set terminator for even list
even->next = NULL;
// Traverse the list
while (odd->next) {
// Store the next node in odd list
Node* temp = odd->next->next;
// Link the next even node at
// the beginning of even list
odd->next->next = even;
even = odd->next;
// Remove the even node from middle
odd->next = temp;
// Move odd to the next odd node
if (temp != NULL)
odd = temp;
}
// Append the even list at the end of odd list
odd->next = even;
}
/* Function to add a node at
the beginning of Linked List */
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;
}
/* Function to print nodes
in a given linked list */
void printList(Node* node)
{
while (node != NULL) {
cout << node->data << " ";
node = node->next;
}
}
/* Driver code */
int main()
{
Node* start = NULL;
/* The constructed linked list is:
1->2->3->4->5->6->7 */
push(&start, 7);
push(&start, 6);
push(&start, 5);
push(&start, 4);
push(&start, 3);
push(&start, 2);
push(&start, 1);
cout << "Linked list before calling rearrange() ";
printList(start);
rearrange(start);
cout << "\nLinked list after calling rearrange() ";
printList(start);
return 0;
}
// This code is contributed by rathbhupendra
C
#include <stdio.h>
#include <stdlib.h>
/* A linked list node */
struct Node {
int data;
struct Node* next;
};
/* Function to reverse all even positioned
node and append at the end
odd is the head node of given linked list */
void rearrange(struct Node* odd)
{
// If linked list has less than 3 nodes,
// no change is required
if (odd == NULL || odd->next == NULL
|| odd->next->next == NULL)
return;
// even points to the beginning of even list
struct Node* even = odd->next;
// Remove the first even node
odd->next = odd->next->next;
// odd points to next node in odd list
odd = odd->next;
// Set terminator for even list
even->next = NULL;
// Traverse the list
while (odd->next) {
// Store the next node in odd list
struct Node* temp = odd->next->next;
// Link the next even node at the
// beginning of even list
odd->next->next = even;
even = odd->next;
// Remove the even node from middle
odd->next = temp;
// Move odd to the next odd node
if (temp != NULL)
odd = temp;
}
// Append the even list at the end of odd list
odd->next = even;
}
/* Function to add a node at the
beginning of Linked List */
void push(struct Node** head_ref,
int new_data)
{
struct Node* new_node
= (struct Node*)malloc(
sizeof(struct Node));
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
/* Function to print nodes in a
given linked list */
void printList(struct Node* node)
{
while (node != NULL) {
printf("%d ", node->data);
node = node->next;
}
}
/* Driver program to test above function */
int main()
{
struct Node* start = NULL;
/* The constructed linked list is:
1->2->3->4->5->6->7 */
push(&start, 7);
push(&start, 6);
push(&start, 5);
push(&start, 4);
push(&start, 3);
push(&start, 2);
push(&start, 1);
printf("\n Linked list before calling rearrange() ");
printList(start);
rearrange(start);
printf("\n Linked list after calling rearrange() ");
printList(start);
return 0;
}
Java
// Java program to reverse alternate
// nodes of a linked list and append
// at the end
class LinkedList {
static Node head;
static class Node {
int data;
Node next;
Node(int item)
{
data = item;
next = null;
}
}
/* Function to reverse all even
positioned node and append at the end
odd is the head node of given linked list */
void rearrange(Node odd)
{
// If linked list has less than 3 nodes,
// no change is required
if (odd == null || odd.next == null
|| odd.next.next == null) {
return;
}
// even points to the beginning
// of even list
Node even = odd.next;
// Remove the first even node
odd.next = odd.next.next;
// odd points to next node in odd list
odd = odd.next;
// Set terminator for even list
even.next = null;
// Traverse the list
while (odd.next != null) {
// Store the next node in odd list
Node temp = odd.next.next;
// Link the next even node at the
// beginning of even list
odd.next.next = even;
even = odd.next;
// Remove the even node from middle
odd.next = temp;
// Move odd to the next odd node
if (temp != null) {
odd = temp;
}
}
// Append the even list at the end of odd list
odd.next = even;
}
/* Function to print nodes in a given linked list */
void printList(Node node)
{
while (node != null) {
System.out.print(node.data + " ");
node = node.next;
}
}
public static void main(String[] args)
{
LinkedList list = new LinkedList();
list.head = new Node(1);
list.head.next = new Node(2);
list.head.next.next = new Node(3);
list.head.next.next.next = new Node(4);
list.head.next.next.next.next = new Node(5);
list.head.next.next.next.next.next = new Node(6);
list.head.next.next.next.next.next.next = new Node(7);
System.out.println("Linked list before calling rearrange : ");
list.printList(head);
System.out.println("");
list.rearrange(head);
System.out.println("Linked list after calling rearrange : ");
list.printList(head);
}
}
Python3
# Python program to reverse alternate nodes and append
# at end
# Extra space allowed - O(1)
# Node Class
class Node:
# Constructor to initialize the node object
def __init__(self, data):
self.data = data
self.next = None
# Linked list class contains node object
class LinkedList:
# Constructor to initialize head
def __init__(self):
self.head = None
# Function to insert a new node at the beginning
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
def rearrange(self):
# If linked list has less than 3 nodes, no change
# is required
odd = self.head
if (odd is None or odd.next is None or
odd.next.next is None):
return
# Even points to the beginning of even list
even = odd.next
# Remove the first even node
odd.next = odd.next.next
# Odd points to next node in odd list
odd = odd.next
# Set terminator for even list
even.next = None
# Traverse the list
while (odd.next):
# Store the next node in odd list
temp = odd.next.next
# Link the next even node at the beginning
# of even list
odd.next.next = even
even = odd.next
# Remove the even node from middle
odd.next = temp
# Move odd to the next odd node
if temp is not None:
odd = temp
# Append the even list at the end of odd list
odd.next = even
# Code execution starts here
if __name__ == '__main__':
start = LinkedList()
# The constructed linked list is ;
# 1->2->3->4->5->6->7
start.push(7)
start.push(6)
start.push(5)
start.push(4)
start.push(3)
start.push(2)
start.push(1)
print ("Linked list before calling rearrange() ")
start.printList()
start.rearrange()
print ("\nLinked list after calling rearrange()")
start.printList()
# This code is contributed by NIkhil Kumar Singh(nickzuck_007)
C#
// C# program to reverse alternate
// nodes of a linked list
// and append at the end
using System;
public class LinkedList {
Node head;
public class Node {
public int data;
public Node next;
public Node(int item)
{
data = item;
next = null;
}
}
/* Function to reverse all even
positioned node and append at the end
odd is the head node of given linked list */
void rearrange(Node odd)
{
// If linked list has less than 3
// nodes, no change is required
if (odd == null || odd.next == null || odd.next.next == null) {
return;
}
// even points to the beginning of even list
Node even = odd.next;
// Remove the first even node
odd.next = odd.next.next;
// odd points to next node in odd list
odd = odd.next;
// Set terminator for even list
even.next = null;
// Traverse the list
while (odd.next != null) {
// Store the next node in odd list
Node temp = odd.next.next;
// Link the next even node at
// the beginning of even list
odd.next.next = even;
even = odd.next;
// Remove the even node from middle
odd.next = temp;
// Move odd to the next odd node
if (temp != null) {
odd = temp;
}
}
// Append the even list at the end of odd list
odd.next = even;
}
/* Function to print nodes in a given linked list */
void printList(Node node)
{
while (node != null) {
Console.Write(node.data + " ");
node = node.next;
}
}
// Driver code
public static void Main()
{
LinkedList list = new LinkedList();
list.head = new Node(1);
list.head.next = new Node(2);
list.head.next.next = new Node(3);
list.head.next.next.next = new Node(4);
list.head.next.next.next.next = new Node(5);
list.head.next.next.next.next.next = new Node(6);
list.head.next.next.next.next.next.next = new Node(7);
Console.WriteLine("Linked list before calling rearrange : ");
list.printList(list.head);
Console.WriteLine("");
list.rearrange(list.head);
Console.WriteLine("Linked list after calling rearrange : ");
list.printList(list.head);
}
}
/* This code contributed by PrinciRaj1992 */
Javascript
<script>
// Javascript program to reverse alternate
// nodes of a linked list and append
// at the end
class Node
{
constructor(item)
{
this.data = item;
this.next = null;
}
}
let head;
// Function to reverse all even positioned
// node and append at the end odd is the
// head node of given linked list
function rearrange(odd)
{
// If linked list has less than 3 nodes,
// no change is required
if (odd == null || odd.next == null ||
odd.next.next == null)
{
return;
}
// Even points to the beginning
// of even list
let even = odd.next;
// Remove the first even node
odd.next = odd.next.next;
// Odd points to next node in odd list
odd = odd.next;
// Set terminator for even list
even.next = null;
// Traverse the list
while (odd.next != null)
{
// Store the next node in odd list
let temp = odd.next.next;
// Link the next even node at the
// beginning of even list
odd.next.next = even;
even = odd.next;
// Remove the even node from middle
odd.next = temp;
// Move odd to the next odd node
if (temp != null)
{
odd = temp;
}
}
// Append the even list at the
// end of odd list
odd.next = even;
}
// Function to print nodes in a
// given linked list
function printList(node)
{
while (node != null)
{
document.write(node.data + " ");
node = node.next;
}
}
// Driver code
head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);
head.next.next.next = new Node(4);
head.next.next.next.next = new Node(5);
head.next.next.next.next.next = new Node(6);
head.next.next.next.next.next.next = new Node(7);
document.write("Linked list before " +
"calling rearrange : <br>");
printList(head);
document.write("<br>");
rearrange(head);
document.write("Linked list after " +
"calling rearrange : <br>");
printList(head);
// This code is contributed by avanitrachhadiya2155
</script>
Producción
Linked list before calling rearrange() 1 2 3 4 5 6 7 Linked list after calling rearrange() 1 3 5 7 6 4 2
Análisis de Complejidad:
- Complejidad temporal: O(n).
El código anterior simplemente atraviesa la lista enlazada dada. Entonces la complejidad del tiempo es O(n) - Espacio Auxiliar: O(1).
No se requiere espacio adicional.
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