Dada una lista doblemente enlazada que contiene n Nodes, donde cada Node está a lo sumo k alejado de su posición objetivo en la lista. El problema es ordenar la lista doblemente enlazada dada.
Por ejemplo, consideremos k es 2, un Node en la posición 7 en la lista doblemente enlazada ordenada, puede estar en las posiciones 5, 6, 7, 8, 9 en la lista doblemente enlazada dada.
Ejemplos:
Enfoque ingenuo: ordene la lista doblemente enlazada dada utilizando la técnica de ordenación por inserción. Al insertar cada elemento en la parte ordenada de la lista, habrá como máximo k intercambios para colocar el elemento en su posición correcta, ya que está como máximo a k pasos de distancia de su posición correcta.
Implementación:
C++
// C++ implementation to sort a k sorted doubly
// linked list
#include<bits/stdc++.h>
using namespace std;
// a node of the doubly linked list
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
// function to sort a k sorted doubly linked list
struct Node* sortAKSortedDLL(struct Node* head, int k)
{
if(head == NULL || head->next == NULL)
return head;
// perform on all the nodes in list
for(Node *i = head->next; i != NULL; i = i->next) {
Node *j = i;
// There will be atmost k swaps for each element in the list
// since each node is k steps away from its correct position
while(j->prev != NULL && j->data < j->prev->data) {
// swap j and j.prev node
Node* temp = j->prev->prev;
Node* temp2 = j->prev;
Node *temp3 = j->next;
j->prev->next = temp3;
j->prev->prev = j;
j->prev = temp;
j->next = temp2;
if(temp != NULL)
temp->next = j;
if(temp3 != NULL)
temp3->prev = temp2;
}
// if j is now the new head
// then reset head
if(j->prev == NULL)
head = j;
}
return head;
}
// Function to insert a node at the beginning
// of the Doubly Linked List
void push(struct Node** head_ref, int new_data)
{
// allocate node
struct Node* new_node =
(struct Node*)malloc(sizeof(struct Node));
// put in the data
new_node->data = new_data;
// since we are adding at the beginning,
// prev is always NULL
new_node->prev = NULL;
// link the old list off the new node
new_node->next = (*head_ref);
// change prev of head node to new node
if ((*head_ref) != NULL)
(*head_ref)->prev = new_node;
// move the head to point to the new node
(*head_ref) = new_node;
}
// Function to print nodes in a given doubly linked list
void printList(struct Node* head)
{
// if list is empty
if (head == NULL)
cout << "Doubly Linked list empty";
while (head != NULL) {
cout << head->data << " ";
head = head->next;
}
}
// Driver program to test above
int main()
{
struct Node* head = NULL;
// Create the doubly linked list:
// 3<->6<->2<->12<->56<->8
push(&head, 8);
push(&head, 56);
push(&head, 12);
push(&head, 2);
push(&head, 6);
push(&head, 3);
int k = 2;
cout << "Original Doubly linked list:\n";
printList(head);
// sort the biotonic DLL
head = sortAKSortedDLL(head, k);
cout << "\nDoubly linked list after sorting:\n";
printList(head);
return 0;
}
// This code is contributed by sachinejain74754.
Java
// Java implementation to sort a k sorted doubly
import java.util.*;
class DoublyLinkedList
{
static Node head;
static class Node
{
int data;
Node next, prev;
Node(int d)
{
data = d;
next = prev = null;
}
}
// function to sort a k sorted doubly linked list
// Using Insertion Sort
// Time Complexity: O(n*k)
// Space Complexity: O(1)
Node sortAKSortedDLL( Node head, int k) {
if(head == null || head.next == null)
return head;
// perform on all the nodes in list
for(Node i = head.next; i != null; i = i.next) {
Node j = i;
// There will be atmost k swaps for each element in the list
// since each node is k steps away from its correct position
while(j.prev != null && j.data < j.prev.data) {
// swap j and j.prev node
Node temp = j.prev.prev;
Node temp2 = j.prev;
Node temp3 = j.next;
j.prev.next = temp3;
j.prev.prev = j;
j.prev = temp;
j.next = temp2;
if(temp != null)
temp.next = j;
if(temp3 != null)
temp3.prev = temp2;
}
// if j is now the new head
// then reset head
if(j.prev == null)
head = j;
}
return head;
}
/* UTILITY FUNCTIONS */
/* Function to insert a node at the beginning of the
* Doubly Linked List */
void push(int new_data)
{
/* allocate node */
Node new_node = new Node(new_data);
/* since we are adding at the beginning,
prev is always NULL */
new_node.prev = null;
/* link the old list off the new node */
new_node.next = head;
/* change prev of head node to new node */
if (head != null)
{
head.prev = new_node;
}
/* move the head to point to the new node */
head = new_node;
}
/* Function to print nodes in a given doubly linked list
This function is same as printList() of singly linked
list */
void printList(Node node)
{
while (node != null)
{
System.out.print(node.data + " ");
node = node.next;
}
}
// Driver code
public static void main(String[] args)
{
DoublyLinkedList list = new DoublyLinkedList();
/* Let us create a k sorted doubly linked list to test the
functions Created doubly linked list will be 3<->6<->2<->12<->56<->8
*/
list.push(8);
list.push(56);
list.push(12);
list.push(2);
list.push(6);
list.push(3);
int k = 2;
System.out.println("Original Doubly linked list:");
list.printList(head);
Node sortedDLL = list.sortAKSortedDLL(head, k);
System.out.println("");
System.out.println("Doubly Linked List after sorting:");
list.printList(sortedDLL);
}
}
// This code is contributed by Mittul Mandhan(@mittulmandhan)
Python3
# Python implementation to sort a k sorted doublyclass DoublyLinkedList {
head = None
class Node:
def __init__(self, val):
self.data = val
self.prev = None
self.next = None
# function to sort a k sorted doubly linked list
# Using Insertion Sort
# Time Complexity: O(n*k)
# Space Complexity: O(1)
def sortAKSortedDLL(head , k):
if (head == None or head.next == None):
return head
# perform on all the nodes in list
i = head.next
while(i != None):
j = i
# There will be atmost k swaps for each element in the list
# since each node is k steps away from its correct position
while (j.prev != None and j.data < j.prev.data):
# swap j and j.prev node
temp = j.prev.prev
temp2 = j.prev
temp3 = j.next
j.prev.next = temp3
j.prev.prev = j
j.prev = temp
j.next = temp2
if (temp != None):
temp.next = j
if (temp3 != None):
temp3.prev = temp2
# if j is now the new head
# then reset head
if (j.prev == None):
head = j
i = i.next
return head
# UTILITY FUNCTIONS
#
# Function to insert a node at the beginning of the Doubly Linked List
def push(new_data):
global head
# allocate node
new_node = Node(new_data)
#
# since we are adding at the beginning, prev is always NULL
#
new_node.prev = None
# link the old list off the new node
new_node.next = head
# change prev of head node to new node
if (head != None):
head.prev = new_node
# move the head to point to the new node
head = new_node
# Function to print nodes in a given doubly linked list This function is same
# as printList() of singly linked list
def printList(node):
while (node != None):
print(node.data,end = " ")
node = node.next
# Driver code
# Let us create a k sorted doubly linked list to test the functions Created
# doubly linked list will be 3<->6<->2<->12<->56<->8
push(8)
push(56)
push(12)
push(2)
push(6)
push(3)
k = 2
print("Original Doubly linked list:")
printList(head)
sortedDLL = sortAKSortedDLL(head, k)
print("")
print("Doubly Linked List after sorting:")
printList(sortedDLL)
# This codeis contributed by shinjanpatra
C#
// C# implementation to sort a k sorted doubly lists
using System;
class DoublyLinkedList {
static Node head;
public class Node {
public int data;
public Node next, prev;
public Node(int d)
{
data = d;
next = prev = null;
}
}
// function to sort a k sorted doubly linked list
// Using Insertion Sort
// Time Complexity: O(n*k)
// Space Complexity: O(1)
public Node sortAKSortedDLL(Node head, int k)
{
if (head == null || head.next == null)
return head;
// perform on all the nodes in list
for (Node i = head.next; i != null; i = i.next) {
Node j = i;
// There will be atmost k swaps for each element
// in the list since each node is k steps away
// from its correct position
while (j.prev != null && j.data < j.prev.data)
{
// swap j and j.prev node
Node temp = j.prev.prev;
Node temp2 = j.prev;
Node temp3 = j.next;
j.prev.next = temp3;
j.prev.prev = j;
j.prev = temp;
j.next = temp2;
if (temp != null)
temp.next = j;
if (temp3 != null)
temp3.prev = temp2;
}
// if j is now the new head
// then reset head
if (j.prev == null)
head = j;
}
return head;
}
/* UTILITY FUNCTIONS */
/* Function to insert a node at the beginning of the
* Doubly Linked List */
public void push(int new_data)
{
/* allocate node */
Node new_node = new Node(new_data);
/* since we are adding at the beginning,
prev is always NULL */
new_node.prev = null;
/* link the old list off the new node */
new_node.next = head;
/* change prev of head node to new node */
if (head != null) {
head.prev = new_node;
}
/* move the head to point to the new node */
head = new_node;
}
/* Function to print nodes in a given doubly linked list
This function is same as printList() of singly linked
list */
public void printList(Node node)
{
while (node != null) {
Console.Write(node.data + " ");
node = node.next;
}
}
// Driver Code
public static void Main(string[] args)
{
DoublyLinkedList list = new DoublyLinkedList();
/* Let us create a k sorted doubly linked list to
test the functions Created doubly linked list
will be 3<->6<->2<->12<->56<->8
*/
list.push(8);
list.push(56);
list.push(12);
list.push(2);
list.push(6);
list.push(3);
int k = 2;
Console.WriteLine("Original Doubly linked list:");
list.printList(head);
Node sortedDLL = list.sortAKSortedDLL(head, k);
Console.WriteLine();
Console.WriteLine(
"Doubly Linked List after sorting:");
list.printList(sortedDLL);
}
}
// This code is contributed by Tapesh (tapeshdua420)
Javascript
<script>
// javascript implementation to sort a k sorted doublyclass DoublyLinkedList {
var head;
class Node {
constructor(val) {
this.data = val;
this.prev = null;
this.next = null;
}
}
// function to sort a k sorted doubly linked list
// Using Insertion Sort
// Time Complexity: O(n*k)
// Space Complexity: O(1)
function sortAKSortedDLL(head , k) {
if (head == null || head.next == null)
return head;
// perform on all the nodes in list
for (i = head.next; i != null; i = i.next) {
var j = i;
// There will be atmost k swaps for each element in the list
// since each node is k steps away from its correct position
while (j.prev != null && j.data < j.prev.data) {
// swap j and j.prev node
var temp = j.prev.prev;
var temp2 = j.prev;
var temp3 = j.next;
j.prev.next = temp3;
j.prev.prev = j;
j.prev = temp;
j.next = temp2;
if (temp != null)
temp.next = j;
if (temp3 != null)
temp3.prev = temp2;
}
// if j is now the new head
// then reset head
if (j.prev == null)
head = j;
}
return head;
}
/* UTILITY FUNCTIONS */
/*
* Function to insert a node at the beginning of the Doubly Linked List
*/
function push(new_data) {
/* allocate node */
var new_node = new Node(new_data);
/*
* since we are adding at the beginning, prev is always NULL
*/
new_node.prev = null;
/* link the old list off the new node */
new_node.next = head;
/* change prev of head node to new node */
if (head != null) {
head.prev = new_node;
}
/* move the head to point to the new node */
head = new_node;
}
/*
* Function to print nodes in a given doubly linked list This function is same
* as printList() of singly linked list
*/
function printList(node) {
while (node != null) {
document.write(node.data + " ");
node = node.next;
}
}
// Driver code
/*
* Let us create a k sorted doubly linked list to test the functions Created
* doubly linked list will be 3<->6<->2<->12<->56<->8
*/
push(8);
push(56);
push(12);
push(2);
push(6);
push(3);
var k = 2;
document.write("Original Doubly linked list:<br/>");
printList(head);
var sortedDLL = sortAKSortedDLL(head, k);
document.write("");
document.write("<br/>Doubly Linked List after sorting:<br/>");
printList(sortedDLL);
// This code contributed by aashish1995
</script>
Producción
Original Doubly linked list: 3 6 2 12 56 8 Doubly Linked List after sorting: 2 3 6 8 12 56
Complejidad temporal: O(n*k)
Espacio auxiliar: O(1)
Enfoque eficiente: podemos ordenar la lista utilizando la estructura de datos MIN HEAP. El enfoque se ha explicado en Ordenar una array casi ordenada (o K ordenada) . Solo debemos tener cuidado al atravesar la lista doblemente enlazada de entrada y ajustar los enlaces siguiente y anterior requeridos en la lista ordenada final.
Implementación:
CPP
// C++ implementation to sort a k sorted doubly
// linked list
#include <bits/stdc++.h>
using namespace std;
// a node of the doubly linked list
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
// 'compare' function used to build up the
// priority queue
struct compare {
bool operator()(struct Node* p1, struct Node* p2)
{
return p1->data > p2->data;
}
};
// function to sort a k sorted doubly linked list
struct Node* sortAKSortedDLL(struct Node* head, int k)
{
// if list is empty
if (head == NULL)
return head;
// priority_queue 'pq' implemented as min heap with the
// help of 'compare' function
priority_queue<Node*, vector<Node*>, compare> pq;
struct Node* newHead = NULL, *last;
// Create a Min Heap of first (k+1) elements from
// input doubly linked list
for (int i = 0; head != NULL && i <= k; i++) {
// push the node on to 'pq'
pq.push(head);
// move to the next node
head = head->next;
}
// loop till there are elements in 'pq'
while (!pq.empty()) {
// place root or top of 'pq' at the end of the
// result sorted list so far having the first node
// pointed to by 'newHead'
// and adjust the required links
if (newHead == NULL) {
newHead = pq.top();
newHead->prev = NULL;
// 'last' points to the last node
// of the result sorted list so far
last = newHead;
}
else {
last->next = pq.top();
pq.top()->prev = last;
last = pq.top();
}
// remove element from 'pq'
pq.pop();
// if there are more nodes left in the input list
if (head != NULL) {
// push the node on to 'pq'
pq.push(head);
// move to the next node
head = head->next;
}
}
// making 'next' of last node point to NULL
last->next = NULL;
// new head of the required sorted DLL
return newHead;
}
// Function to insert a node at the beginning
// of the Doubly Linked List
void push(struct Node** head_ref, int new_data)
{
// allocate node
struct Node* new_node =
(struct Node*)malloc(sizeof(struct Node));
// put in the data
new_node->data = new_data;
// since we are adding at the beginning,
// prev is always NULL
new_node->prev = NULL;
// link the old list off the new node
new_node->next = (*head_ref);
// change prev of head node to new node
if ((*head_ref) != NULL)
(*head_ref)->prev = new_node;
// move the head to point to the new node
(*head_ref) = new_node;
}
// Function to print nodes in a given doubly linked list
void printList(struct Node* head)
{
// if list is empty
if (head == NULL)
cout << "Doubly Linked list empty";
while (head != NULL) {
cout << head->data << " ";
head = head->next;
}
}
// Driver program to test above
int main()
{
struct Node* head = NULL;
// Create the doubly linked list:
// 3<->6<->2<->12<->56<->8
push(&head, 8);
push(&head, 56);
push(&head, 12);
push(&head, 2);
push(&head, 6);
push(&head, 3);
int k = 2;
cout << "Original Doubly linked list:\n";
printList(head);
// sort the biotonic DLL
head = sortAKSortedDLL(head, k);
cout << "\nDoubly linked list after sorting:\n";
printList(head);
return 0;
}
Java
// Java implementation to sort a k sorted doubly
import java.util.*;
class DoublyLinkedList
{
static Node head;
static class Node
{
int data;
Node next, prev;
Node(int d)
{
data = d;
next = prev = null;
}
}
class compareNode implements Comparator<Node>
{
public int compare(Node n1, Node n2){
return n1.data-n2.data;
}
}
// function to sort a k sorted doubly linked list
Node sortAKSortedDLL( Node head, int k)
{
// if list is empty
if (head == null)
return head;
// priority_queue 'pq' implemented as min heap with the
// help of 'compare' function in compare Node class
PriorityQueue<Node> pq = new PriorityQueue<Node>(new compareNode());
Node newHead = null, last = null;
// Create a Min Heap of first (k+1) elements from
// input doubly linked list
for (int i = 0; head != null && i <= k; i++)
{
// push the node on to 'pq'
pq.add(head);
// move to the next node
head = head.next;
}
// loop till there are elements in 'pq'
while (!pq.isEmpty())
{
// place root or top of 'pq' at the end of the
// result sorted list so far having the first node
// pointed to by 'newHead'
// and adjust the required links
if (newHead == null)
{
newHead = pq.peek();
newHead.prev = null;
// 'last' points to the last node
// of the result sorted list so far
last = newHead;
}
else
{
last.next = pq.peek();
pq.peek().prev = last;
last = pq.peek();
}
// remove element from 'pq'
pq.poll();
// if there are more nodes left in the input list
if (head != null)
{
// push the node on to 'pq'
pq.add(head);
// move to the next node
head = head.next;
}
}
// making 'next' of last node point to NULL
last.next = null;
// new head of the required sorted DLL
return newHead;
}
/* UTILITY FUNCTIONS */
/* Function to insert a node at the beginning of the
* Doubly Linked List */
void push(int new_data)
{
/* allocate node */
Node new_node = new Node(new_data);
/* since we are adding at the beginning,
prev is always NULL */
new_node.prev = null;
/* link the old list off the new node */
new_node.next = head;
/* change prev of head node to new node */
if (head != null)
{
head.prev = new_node;
}
/* move the head to point to the new node */
head = new_node;
}
/* Function to print nodes in a given doubly linked list
This function is same as printList() of singly linked
list */
void printList(Node node)
{
while (node != null)
{
System.out.print(node.data + " ");
node = node.next;
}
}
// Driver code
public static void main(String[] args)
{
DoublyLinkedList list = new DoublyLinkedList();
/* Let us create a k sorted doubly linked list to test the
functions Created doubly linked list will be 3<->6<->2<->12<->56<->8
*/
list.push(8);
list.push(56);
list.push(12);
list.push(2);
list.push(6);
list.push(3);
int k = 2;
System.out.println("Original Doubly linked list:");
list.printList(head);
Node sortedDLL = list.sortAKSortedDLL(head, k);
System.out.println("");
System.out.println("Doubly Linked List after sorting:");
list.printList(sortedDLL);
}
}
// This code is contributed by Kushagra Keserwani
Python3
# Python implementation to sort a k sorted doubly linked list
import heapq
head = None
# a node of the doubly linked list
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
# function to sort a k sorted doubly linked list
def sortAKSortedDLL(head, k):
# if list is empty
if head == None:
return head
pq = []
newHead = None
last = None
for i in range(k+1):
# push the node
heapq.heappush(pq, (head.data, head))
# move to the next node
head = head.next
# loop till there are elements in 'pq'
while len(pq) > 0:
if newHead == None:
newHead = heapq.heappop(pq)[1]
newHead.prev = None
# 'last' points to the last node of the result sorted list so far
last = newHead
else:
last.next = heapq.heappop(pq)[1]
last.next.prev = last
last = last.next
# if there are more nodes left in the input list
if head != None:
# push the node
heapq.heappush(pq, (head.data, head))
# move to the next node
head = head.next
# making 'next' of last node point to NULL
last.next = None
# new head of the required sorted DLL
return newHead
# Function to insert a node at the beginning of the Doubly Linked List
def push(new_data):
global head
# allocate node
new_node = Node(new_data)
# since we are adding at the beginning, prev is always NULL
new_node.prev = None
# link the old list off the new node
new_node.next = head
# change prev of head node to new node
if (head != None):
head.prev = new_node
# move the head to point to the new node
head = new_node
# Function to print nodes in a given doubly linked list
def printList(head):
# if list is empty
if head is None:
print("Doubly Linked list empty")
while head is not None:
print(head.data, end=" ")
head = head.next
# Driver code
if __name__ == '__main__':
# Create the doubly linked list:
# 3<->6<->2<->12<->56<->8
push(8)
push(56)
push(12)
push(2)
push(6)
push(3)
k = 2
print("Original Doubly linked list:")
printList(head)
sortedDLL = sortAKSortedDLL(head, k)
print("\nDoubly Linked List after sorting:")
printList(sortedDLL)
# This code is contributed by Tapesh(tapeshdua420)
Producción
Original Doubly linked list: 3 6 2 12 56 8 Doubly linked list after sorting: 2 3 6 8 12 56
Complejidad de Tiempo: O(n*log k)
Espacio Auxiliar: O(k)
Este artículo es una contribución de Ayush Jauhari . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
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