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.
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