Dada la cabeza y la cola de una lista doblemente enlazada que contiene 0 y 1 , la tarea es ordenar la lista doblemente enlazada sin modificar los datos.
Ejemplos :
Entrada : cabeza = 1->1->0->0->1->0->1->1->0->0->NULL
Salida : 0->0->0->0->0 ->1->1->1->1->1->NULOEntrada : cabeza = 1->0->NULL
Salida : 0->1->NULL
Enfoque : la idea para resolver este problema es usar el algoritmo de dos punteros como se menciona a continuación:
- Cree dos punteros: cabeza y cola, de modo que la cabeza apunte al primer elemento y la cola apunte al último elemento
- Siga revisando el elemento en los punteros para 1 en la cabeza y 0 en la cola,
- Intercambie los elementos siempre que se encuentre la combinación 1, 0.
Siga los pasos para resolver el problema:
- Inicializar primer puntero = cabeza, último puntero = cola
- Mientras que primero != último y primero -> anterior != último
- Comprobar, si primero->datos == 0
- actualizar, primero = primero->siguiente
- Si, último->datos == 1
- actualizar, último = último->anterior
- Si, primero->datos == 1 y último->datos == 0
- luego , intercambie el primer y el último Node
- cambiar de nuevo el primer y el último puntero
- moverse primero hacia la derecha y el último hacia la izquierda por 1
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach: #include <iostream> using namespace std; // Link list Node Class class Node { public: int data; Node* prev; Node* next; // Constructor function Node(int data) { this->data = data; this->prev = NULL; this->next = NULL; } }; // Function to print linked list void print(Node* head) { Node* temp = head; // Iterate until node is NOT NULL while (temp != NULL) { cout << temp->data << " "; temp = temp->next; } cout << endl; } // Function to push a node in // Doubly linked- list void push(Node*& head, Node*& tail, int item) { // If list is empty if (tail == NULL) { Node* temp = new Node(item); tail = temp; head = temp; } // List is not empty else { Node* temp = new Node(item); tail->next = temp; temp->prev = tail; tail = temp; } } // Function to swap the list // Consisting of 0s and 1s void swap(Node*& Node1, Node*& Node2) { Node* temp; temp = Node1->next; Node1->next = Node2->next; Node2->next = temp; if (Node1->next != NULL) Node1->next->prev = Node1; if (Node2->next != NULL) Node2->next->prev = Node2; temp = Node1->prev; Node1->prev = Node2->prev; Node2->prev = temp; if (Node1->prev != NULL) Node1->prev->next = Node1; if (Node2->prev != NULL) Node2->prev->next = Node2; } // Function to sort the list // Consisting of 0s and 1s void sort(Node*& head, Node*& tail) { // Base Case if (head == tail || head == NULL) return; // Initialize the pointers Node* first = head; Node* last = tail; while ((first != last) && (first->prev != last)) { // If first->data is 0 then move // First towards right by 1 if (first->data == 0) first = first->next; // If last->data is 1 then move // Last towards left by 1 if (last->data == 1) last = last->prev; // If first->data is 1 and last->data is 0 // then swap first and last node if (first->data == 1 && last->data == 0 && first->prev != last) { // Swapping the node swap(first, last); // if head = 1 if (head == first) head = last; // if tail == 0 if (tail == last) tail = first; // Swapping the pointer and // moved to next iteration Node* Temp = first; first = last->next; last = Temp->prev; } } } // Driver Code int main() { Node* head = NULL; Node* tail = NULL; push(head, tail, 1); push(head, tail, 1); push(head, tail, 0); push(head, tail, 0); push(head, tail, 1); push(head, tail, 0); push(head, tail, 1); push(head, tail, 1); push(head, tail, 0); push(head, tail, 0); sort(head, tail); print(head); return 0; }
Java
// Java program for the above approach: import java.util.*; class GFG{ static Node head; static Node tail; // Link list Node Class static class Node { int data; Node prev; Node next; // Constructor function Node(int data) { this.data = data; this.prev = null; this.next = null; } }; // Function to print linked list static void print(Node head) { Node temp = head; // Iterate until node is NOT null while (temp != null) { System.out.print(temp.data+ " "); temp = temp.next; } System.out.println(); } // Function to push a node in // Doubly linked- list static void push(int item) { // If list is empty if (tail == null) { Node temp = new Node(item); tail = temp; head = temp; } // List is not empty else { Node temp = new Node(item); tail.next = temp; temp.prev = tail; tail = temp; } } // Function to swap the list // Consisting of 0s and 1s static void swap(Node Node1, Node Node2) { Node temp; temp = Node1.next; Node1.next = Node2.next; Node2.next = temp; if (Node1.next != null) Node1.next.prev = Node1; if (Node2.next != null) Node2.next.prev = Node2; temp = Node1.prev; Node1.prev = Node2.prev; Node2.prev = temp; if (Node1.prev != null) Node1.prev.next = Node1; if (Node2.prev != null) Node2.prev.next = Node2; } // Function to sort the list // Consisting of 0s and 1s static void sort() { // Base Case if (head == tail || head == null) return; // Initialize the pointers Node first = head; Node last = tail; while ((first != last) && (first.prev != last)) { // If first.data is 0 then move // First towards right by 1 if (first.data == 0) first = first.next; // If last.data is 1 then move // Last towards left by 1 if (last.data == 1) last = last.prev; // If first.data is 1 and last.data is 0 // then swap first and last node if (first.data == 1 && last.data == 0 && first.prev != last) { // Swapping the node swap(first, last); // if head = 1 if (head == first) head = last; // if tail == 0 if (tail == last) tail = first; // Swapping the pointer and // moved to next iteration Node Temp = first; first = last.next; last = Temp.prev; } } } // Driver Code public static void main(String[] args) { push(1); push(1); push(0); push(0); push(1); push(0); push(1); push(1); push(0); push(0); sort(); print(head); } } // This code is contributed by 29AjayKumar
Python3
# Python code for the above approach # Node Class class Node: def __init__(self, d): self.data = d self.next = None self.prev = None class LinkedList: def __init__(self): self.head = None self.tail = None ## Function to push a node in ## Doubly linked list def push(self, d): ## If list is empty if (self.tail == None): temp = Node(d); self.head = temp; self.tail = temp; else: ## Non-empty list temp = Node(d); self.tail.next = temp temp.prev = self.tail self.tail = temp ## Function to print Doubly linked list def printList(self): curr = self.head if(self.head == None): print("List is Empty") return ## Else iterate until node is NOT None print(curr.data, " ", end='') curr = curr.next while curr != None: print(curr.data, " ", end='') curr = curr.next print("\n") ## Function to swap the list ## Consisting of 0s and 1s def swap(self, Node1, Node2): temp = None temp = Node1.next Node1.next = Node2.next Node2.next = temp if (Node1.next != None): Node1.next.prev = Node1 if (Node2.next != None): Node2.next.prev = Node2 temp = Node1.prev Node1.prev = Node2.prev Node2.prev = temp if (Node1.prev != None): Node1.prev.next = Node1 if (Node2.prev != None): Node2.prev.next = Node2 ## Function to sort the list ## Consisting of 0s and 1s def sort(self): ## Base Case if (self.head == self.tail or self.head == None): return; ## Initialize the pointers first = self.head last = self.tail while ((first != last) and (first.prev != last)): ## If first.data is 0 then move ## First towards right by 1 if (first.data == 0): first = first.next ## If last.data is 1 then move ## Last towards left by 1 if (last.data == 1): last = last.prev ## If first.data is 1 and last.data is 0 ## then swap first and last node if (first.data == 1 and last.data == 0 and first.prev != last): ## Swapping the node self.swap(first, last); ## if head = 1 if (self.head == first): self.head = last; ## if tail == 0 if (self.tail == last): self.tail = first ## Swapping the pointer and ## moved to next iteration Temp = first first = last.next; last = Temp.prev; # Driver Code if __name__=='__main__': llist = LinkedList() llist.push(1) llist.push(1) llist.push(0) llist.push(0) llist.push(1) llist.push(0) llist.push(1) llist.push(1) llist.push(0) llist.push(0) llist.sort() llist.printList() # This code is contributed by subhamgoyal2014.
C#
// C# program for the above approach: using System; using System.Collections.Generic; public class GFG{ static Node head; static Node tail; // Link list Node Class public class Node { public int data; public Node prev; public Node next; // Constructor function public Node(int data) { this.data = data; this.prev = null; this.next = null; } }; // Function to print linked list static void print(Node head) { Node temp = head; // Iterate until node is NOT null while (temp != null) { Console.Write(temp.data+ " "); temp = temp.next; } Console.WriteLine(); } // Function to push a node in // Doubly linked- list static void push(int item) { // If list is empty if (tail == null) { Node temp = new Node(item); tail = temp; head = temp; } // List is not empty else { Node temp = new Node(item); tail.next = temp; temp.prev = tail; tail = temp; } } // Function to swap the list // Consisting of 0s and 1s static void swap(Node Node1, Node Node2) { Node temp; temp = Node1.next; Node1.next = Node2.next; Node2.next = temp; if (Node1.next != null) Node1.next.prev = Node1; if (Node2.next != null) Node2.next.prev = Node2; temp = Node1.prev; Node1.prev = Node2.prev; Node2.prev = temp; if (Node1.prev != null) Node1.prev.next = Node1; if (Node2.prev != null) Node2.prev.next = Node2; } // Function to sort the list // Consisting of 0s and 1s static void sort() { // Base Case if (head == tail || head == null) return; // Initialize the pointers Node first = head; Node last = tail; while ((first != last) && (first.prev != last)) { // If first.data is 0 then move // First towards right by 1 if (first.data == 0) first = first.next; // If last.data is 1 then move // Last towards left by 1 if (last.data == 1) last = last.prev; // If first.data is 1 and last.data is 0 // then swap first and last node if (first.data == 1 && last.data == 0 && first.prev != last) { // Swapping the node swap(first, last); // if head = 1 if (head == first) head = last; // if tail == 0 if (tail == last) tail = first; // Swapping the pointer and // moved to next iteration Node Temp = first; first = last.next; last = Temp.prev; } } } // Driver Code public static void Main(String[] args) { push(1); push(1); push(0); push(0); push(1); push(0); push(1); push(1); push(0); push(0); sort(); print(head); } } // This code is contributed by shikhasingrajput
Producción
0 0 0 0 0 1 1 1 1 1
Complejidad de Tiempo : O(N)
Espacio Auxiliar : O(1)
Publicación traducida automáticamente
Artículo escrito por akashjha2671 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA