Dada una lista enlazada que contiene n Nodes. El problema es reorganizar los Nodes de la lista de tal manera que los datos en el primer Node sean el primer mínimo, el segundo Node sea el primer máximo, el tercer Node sea el segundo mínimo, el cuarto Node sea el segundo máximo y así sucesivamente.
Ejemplos:
Input : list: 4->1->3->5->2 Output : 1->5->2->4->3 Input : list: 10->9->8->7->6->5 Output : 5->10->6->9->7->8
Enfoque: Los siguientes son los pasos:
- Ordene la lista enlazada utilizando la técnica Merge Sort .
- Divida la lista en listas delanteras y traseras . Consulte FrontBackProcedure de esta publicación.
- Ahora, invierta la lista anterior . Consulte esta publicación.
- Finalmente, fusione los Nodes de las listas primera y última en orden alternativo.
Implementación
CPP
// C++ implementation of alternative sorting
// of the Linked list
#include <bits/stdc++.h>
using namespace std;
// node of a linked list
struct Node {
int data;
struct Node* next;
};
// function to get a new node
Node* getNode(int data)
{
// allocate space for node
Node* newNode = (Node*)malloc(sizeof(Node));
// put in the data
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// Split the nodes of the given list into front and
// back halves, and return the two lists using the
// reference parameters. If the length is odd, the
// extra node should go in the front list. Uses the
// fast/slow pointer strategy.
void FrontBackSplit(Node* source,
Node** frontRef, Node** backRef)
{
Node* fast;
Node* slow;
if (source == NULL || source->next == NULL) {
// length < 2 cases
*frontRef = source;
*backRef = NULL;
}
else {
slow = source;
fast = source->next;
// Advance 'fast' two nodes, and
// advance 'slow' one node
while (fast != NULL) {
fast = fast->next;
if (fast != NULL) {
slow = slow->next;
fast = fast->next;
}
}
// 'slow' is before the midpoint in the list,
// so split it in two at that point.
*frontRef = source;
*backRef = slow->next;
slow->next = NULL;
}
}
// function to merge two sorted lists in
// sorted order
Node* SortedMerge(Node* a, Node* b)
{
Node* result = NULL;
// Base cases
if (a == NULL)
return b;
else if (b == NULL)
return a;
// Pick either a or b, and recur
if (a->data <= b->data) {
result = a;
result->next = SortedMerge(a->next, b);
}
else {
result = b;
result->next = SortedMerge(a, b->next);
}
return result;
}
// sorts the linked list by changing
// next pointers (not data)
void MergeSort(Node** headRef)
{
Node* head = *headRef;
Node *a, *b;
// Base case -- length 0 or 1
if ((head == NULL) || (head->next == NULL))
return;
// Split head into 'a' and 'b' sublists
FrontBackSplit(head, &a, &b);
// Recursively sort the sublists
MergeSort(&a);
MergeSort(&b);
// merge the two sorted lists together
*headRef = SortedMerge(a, b);
}
// function to reverse the linked list
static void reverse(Node** head_ref)
{
Node* prev = NULL;
Node* current = *head_ref;
Node* next;
while (current != NULL) {
next = current->next;
current->next = prev;
prev = current;
current = next;
}
*head_ref = prev;
}
// function to alternately merge two lists
void alternateMerge(Node* head1, Node* head2)
{
Node *p, *q;
while (head1 != NULL && head2 != NULL) {
// merging nodes alternately by
// making the desired links
p = head1->next;
head1->next = head2;
head1 = p;
q = head2->next;
head2->next = head1;
head2 = q;
}
}
// function for alternative sort of the
// linked list
Node* altSortForLinkedList(Node* head)
{
// sort the linked list
MergeSort(&head);
Node *front, *back;
// Split head into 'front' and 'back' sublists
FrontBackSplit(head, &front, &back);
// reversing the 'back' list
reverse(&back);
// merging the nodes of 'front' and 'back'
// lists alternately
alternateMerge(front, back);
// required head of final list
return front;
}
// Function to print nodes in
// a given linked list
void printList(Node* head)
{
while (head != NULL) {
cout << head->data << " ";
head = head->next;
}
}
// Driver program to test above
int main()
{
// linked list: 10->9->8->7->6->5
Node* head = getNode(10);
head->next = getNode(9);
head->next->next = getNode(8);
head->next->next->next = getNode(7);
head->next->next->next->next = getNode(6);
head->next->next->next->next->next = getNode(5);
cout << "Original list: ";
printList(head);
head = altSortForLinkedList(head);
cout << "\nModified list: ";
printList(head);
return 0;
}
Producción
Original list: 10 9 8 7 6 5 Modified list: 5 10 6 9 7 8
Complejidad temporal: O(n*logn).
Publicación traducida automáticamente
Artículo escrito por ayushjauhari14 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA