Dada una lista enlazada. organice la lista enlazada en forma de primer y último elemento alternativo.
Ejemplos:
Input : 1->2->3->4->5->6->7->8 Output :1->8->2->7->3->6->4->5 Input :10->11->15->13 Output :10->13->11->15
Hemos discutido tres soluciones diferentes en Reorganizar una lista enlazada dada en el lugar.
En esta publicación se analiza una solución diferente basada en Deque .
Método:
- Crear un deque vacío
- Insertar todos los elementos de la lista enlazada a la deque
- Vuelva a insertar el elemento en la lista enlazada de deque de forma alternativa, es decir, primero, luego último, y así sucesivamente.
Implementación:
C++
// CPP program to rearrange a linked list in given manner
#include <bits/stdc++.h>
using namespace std;
/* Link list node */
struct Node {
int data;
struct Node* next;
};
/* Function to reverse the linked list */
void arrange(struct Node* head)
{
struct Node* temp = head;
deque<int> d; // defining a deque
// push all the elements of linked list in to deque
while (temp != NULL) {
d.push_back(temp->data);
temp = temp->next;
}
// Alternatively push the first and last elements
// from deque to back to the linked list and pop
int i = 0;
temp = head;
while (!d.empty()) {
if (i % 2 == 0) {
temp->data = d.front();
d.pop_front();
}
else {
temp->data = d.back();
d.pop_back();
}
i++;
temp = temp->next; // increase temp
}
}
/*UTILITY FUNCTIONS*/
/* Push a node to linked list. Note that this function
changes the head */
void push(struct Node** head_ref, char new_data)
{
/* allocate node */
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
/* put in the data */
new_node->data = new_data;
/* link the old list off the new node */
new_node->next = (*head_ref);
/* move the head to point to the new node */
(*head_ref) = new_node;
}
// printing the linked list
void printList(struct Node* head)
{
struct Node* temp = head;
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
}
/* Driver program to test above function*/
int main()
{
// Let us create linked list 1->2->3->4
struct Node* head = NULL;
push(&head, 5);
push(&head, 4);
push(&head, 3);
push(&head, 2);
push(&head, 1);
cout << "Given linked list\t";
printList(head);
arrange(head);
cout << "\nAfter rearrangement\t";
printList(head);
return 0;
}
Java
// Java program to rearrange a linked list in given manner
import java.util.*;
import java.lang.*;
import java.io.*;
class GFG
{
/* Link list node */
static class Node
{
int data;
Node next;
Node(int data)
{
this.data = data;
next = null;
}
}
// printing the linked list
static void printList(Node head)
{
Node temp = head;
while (temp != null)
{
System.out.print(temp.data + " ");
temp = temp.next;
}
}
/* Function to reverse the linked list */
static void arrange(Node head)
{
// defining a deque
Deque<Integer> deque = new ArrayDeque<>();
Node temp = head;
// push all the elements of linked list in to deque
while(temp != null)
{
deque.addLast(temp.data);
temp = temp.next;
}
temp = head;
int i = 0;
// Alternatively push the first and last elements
// from deque to back to the linked list and pop
while(!deque.isEmpty())
{
if(i % 2 == 0)
{
temp.data = deque.removeFirst();
}
else
{
temp.data = deque.removeLast();
}
i++;
temp = temp.next;
}
}
// Driver code
public static void main (String[] args)
{
// Let us create linked list 1->2->3->4->5
Node head = null;
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);
System.out.println("Given linked list");
printList(head);
arrange(head);
System.out.println("\nAfter rearrangement");
printList(head);
}
}
// This code is contributed by nobody_cares.
Python
# Python program to rearrange
# a linked list in given manner
# Link list node
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Function to reverse the linked list
def arrange( head):
temp = head
# defining a deque
d = []
# push all the elements of linked list in to deque
while (temp != None) :
d.append(temp.data)
temp = temp.next
# Alternatively push the first and last elements
# from deque to back to the linked list and pop
i = 0
temp = head
while (len(d) > 0) :
if (i % 2 == 0) :
temp.data = d[0]
d.pop(0)
else :
temp.data = d[-1]
d.pop()
i = i + 1
# increase temp
temp = temp.next
return head
# UTILITY FUNCTIONS
# Push a node to linked list. Note that this function
# changes the head
def push( head_ref, new_data):
# allocate node
new_node = Node(0)
# put in the data
new_node.data = new_data
# link the old list off the new node
new_node.next = (head_ref)
# move the head to point to the new node
(head_ref) = new_node
return head_ref
# printing the linked list
def printList( head):
temp = head
while (temp != None) :
print( temp.data,end=" ")
temp = temp.next
# Driver program to test above function
# Let us create linked list 1.2.3.4
head = None
head = push(head, 5)
head = push(head, 4)
head = push(head, 3)
head = push(head, 2)
head = push(head, 1)
print("Given linked list\t")
printList(head)
head = arrange(head)
print( "\nAfter rearrangement\t")
printList(head)
# This code is contributed by Arnab Kundu
Javascript
<script>
// Javascript program to rearrange a linked list in given manner
/* Link list node */
class Node {
constructor()
{
this.data = 0;
this.next = null;
}
};
/* Function to reverse the linked list */
function arrange( head)
{
var temp = head;
var d = []; // defining a deque
// push all the elements of linked list in to deque
while (temp != null) {
d.push(temp.data);
temp = temp.next;
}
// Alternatively push the first and last elements
// from deque to back to the linked list and pop
var i = 0;
temp = head;
while (d.length!=0) {
if (i % 2 == 0) {
temp.data = d[0];
d.shift();
}
else {
temp.data = d[d.length-1];
d.pop();
}
i++;
temp = temp.next; // increase temp
}
}
/*UTILITY FUNCTIONS*/
/* Push a node to linked list. Note that this function
changes the head */
function push(head_ref, new_data)
{
/* allocate node */
var new_node = new Node();
/* put in the data */
new_node.data = new_data;
/* link the old list off the new node */
new_node.next = (head_ref);
/* move the head to point to the new node */
(head_ref) = new_node;
return head_ref;
}
// printing the linked list
function printList(head)
{
var temp = head;
while (temp != null) {
document.write(temp.data+ " ");
temp = temp.next;
}
}
/* Driver program to test above function*/
// Let us create linked list 1.2.3.4
var head = null;
head = push(head, 5);
head = push(head, 4);
head = push(head, 3);
head = push(head, 2);
head = push(head, 1);
document.write( "Given linked list ");
printList(head);
arrange(head);
document.write( "<br>After rearrangement ");
printList(head);
</script>
Producción
Given linked list 1 2 3 4 5 After rearrangement 1 5 2 4 3
Complejidad de tiempo : O(n)
Publicación traducida automáticamente
Artículo escrito por Shahnawaz_Ali y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA