Dada una lista enlazada que se ordena en función de valores absolutos. Ordene la lista según los valores reales.
Ejemplos:
C++
// C++ program to sort a linked list, already
// sorted by absolute values
#include <bits/stdc++.h>
using namespace std;
// Linked List Node
struct Node
{
Node* next;
int data;
};
// Utility function to insert a node at the
// beginning
void push(Node** head, int data)
{
Node* newNode = new Node;
newNode->next = (*head);
newNode->data = data;
(*head) = newNode;
}
// Utility function to print a linked list
void printList(Node* head)
{
while (head != NULL)
{
cout << head->data;
if (head->next != NULL)
cout << " -> ";
head = head->next;
}
cout<<endl;
}
// To sort a linked list by actual values.
// The list is assumed to be sorted by absolute
// values.
void sortList(Node** head)
{
// Initialize previous and current nodes
Node* prev = (*head);
Node* curr = (*head)->next;
// Traverse list
while (curr != NULL)
{
// If curr is smaller than prev, then
// it must be moved to head
if (curr->data < prev->data)
{
// Detach curr from linked list
prev->next = curr->next;
// Move current node to beginning
curr->next = (*head);
(*head) = curr;
// Update current
curr = prev;
}
// Nothing to do if current element
// is at right place
else
prev = curr;
// Move current
curr = curr->next;
}
}
// Driver code
int main()
{
Node* head = NULL;
push(&head, -5);
push(&head, 5);
push(&head, 4);
push(&head, 3);
push(&head, -2);
push(&head, 1);
push(&head, 0);
cout << "Original list :\n";
printList(head);
sortList(&head);
cout << "\nSorted list :\n";
printList(head);
return 0;
}
Java
// Java program to sort a linked list, already
// sorted by absolute values
class SortList
{
static Node head; // head of list
/* Linked list Node*/
static class Node
{
int data;
Node next;
Node(int d) {data = d; next = null; }
}
// To sort a linked list by actual values.
// The list is assumed to be sorted by absolute
// values.
Node sortedList(Node head)
{
// Initialize previous and current nodes
Node prev = head;
Node curr = head.next;
// Traverse list
while(curr != null)
{
// If curr is smaller than prev, then
// it must be moved to head
if(curr.data < prev.data)
{
// Detach curr from linked list
prev.next = curr.next;
// Move current node to beginning
curr.next = head;
head = curr;
// Update current
curr = prev;
}
// Nothing to do if current element
// is at right place
else
prev = curr;
// Move current
curr = curr.next;
}
return head;
}
/* Inserts a new Node at front of the list. */
public void push(int new_data)
{
/* 1 & 2: Allocate the Node &
Put in the data*/
Node new_node = new Node(new_data);
/* 3. Make next of new Node as head */
new_node.next = head;
/* 4. Move the head to point to new Node */
head = new_node;
}
/* Function to print linked list */
void printList(Node head)
{
Node temp = head;
while (temp != null)
{
System.out.print(temp.data+" ");
temp = temp.next;
}
System.out.println();
}
/* Driver program to test above functions */
public static void main(String args[])
{
SortList llist = new SortList();
/* Constructed Linked List is 1->2->3->4->5->6->
7->8->8->9->null */
llist.push(-5);
llist.push(5);
llist.push(4);
llist.push(3);
llist.push(-2);
llist.push(1);
llist.push(0);
System.out.println("Original List :");
llist.printList(llist.head);
llist.head = llist.sortedList(head);
System.out.println("Sorted list :");
llist.printList(llist.head);
}
}
// This code has been contributed by Amit Khandelwal(Amit Khandelwal 1).
Python3
# Python3 program to sort a linked list,
# already sorted by absolute values
# Linked list Node
class Node:
def __init__(self, d):
self.data = d
self.next = None
class SortList:
def __init__(self):
self.head = None
# To sort a linked list by actual values.
# The list is assumed to be sorted by
# absolute values.
def sortedList(self, head):
# Initialize previous and
# current nodes
prev = self.head
curr = self.head.next
# Traverse list
while(curr != None):
# If curr is smaller than prev,
# then it must be moved to head
if(curr.data < prev.data):
# Detach curr from linked list
prev.next = curr.next
# Move current node to beginning
curr.next = self.head
self.head = curr
# Update current
curr = prev
# Nothing to do if current element
# is at right place
else:
prev = curr
# Move current
curr = curr.next
return self.head
# Inserts a new Node at front of the list
def push(self, new_data):
# 1 & 2: Allocate the Node &
# Put in the data
new_node = Node(new_data)
# 3. Make next of new Node as head
new_node.next = self.head
# 4. Move the head to point to new Node
self.head = new_node
# Function to print linked list
def printList(self, head):
temp = head
while (temp != None):
print(temp.data, end = " ")
temp = temp.next
print()
# Driver Code
llist = SortList()
# Constructed Linked List is
# 1->2->3->4->5->6->7->8->8->9->null
llist.push(-5)
llist.push(5)
llist.push(4)
llist.push(3)
llist.push(-2)
llist.push(1)
llist.push(0)
print("Original List :")
llist.printList(llist.head)
start = llist.sortedList(llist.head)
print("Sorted list :")
llist.printList(start)
# This code is contributed by
# Prerna Saini
C#
// C# program to sort a linked list, already
// sorted by absolute values
using System;
public class SortList
{
Node head; // head of list
/* Linked list Node*/
class Node
{
public int data;
public Node next;
public Node(int d)
{
data = d; next = null;
}
}
// To sort a linked list by actual values.
// The list is assumed to be sorted by absolute
// values.
Node sortedList(Node head)
{
// Initialize previous and current nodes
Node prev = head;
Node curr = head.next;
// Traverse list
while(curr != null)
{
// If curr is smaller than prev, then
// it must be moved to head
if(curr.data < prev.data)
{
// Detach curr from linked list
prev.next = curr.next;
// Move current node to beginning
curr.next = head;
head = curr;
// Update current
curr = prev;
}
// Nothing to do if current element
// is at right place
else
prev = curr;
// Move current
curr = curr.next;
}
return head;
}
/* Inserts a new Node at front of the list. */
public void push(int new_data)
{
/* 1 & 2: Allocate the Node &
Put in the data*/
Node new_node = new Node(new_data);
/* 3. Make next of new Node as head */
new_node.next = head;
/* 4. Move the head to point to new Node */
head = new_node;
}
/* Function to print linked list */
void printList(Node head)
{
Node temp = head;
while (temp != null)
{
Console.Write(temp.data + " ");
temp = temp.next;
}
Console.WriteLine();
}
/* Driver code */
public static void Main(String []args)
{
SortList llist = new SortList();
/* Constructed Linked List is 1->2->3->
4->5->6->7->8->8->9->null */
llist.push(-5);
llist.push(5);
llist.push(4);
llist.push(3);
llist.push(-2);
llist.push(1);
llist.push(0);
Console.WriteLine("Original List :");
llist.printList(llist.head);
llist.head = llist.sortedList(llist.head);
Console.WriteLine("Sorted list :");
llist.printList(llist.head);
}
}
/* This code is contributed by 29AjayKumar */
Javascript
<script>
// Javascript program to sort a linked list, already
// sorted by absolute values
var head; // head of list
/* Linked list Node */
class Node {
constructor(d) {
this.data = d;
this.next = null;
}
}
// To sort a linked list by actual values.
// The list is assumed to be sorted by absolute
// values.
function sortedList(head) {
// Initialize previous and current nodes
var prev = head;
var curr = head.next;
// Traverse list
while (curr != null) {
// If curr is smaller than prev, then
// it must be moved to head
if (curr.data < prev.data) {
// Detach curr from linked list
prev.next = curr.next;
// Move current node to beginning
curr.next = head;
head = curr;
// Update current
curr = prev;
}
// Nothing to do if current element
// is at right place
else
prev = curr;
// Move current
curr = curr.next;
}
return head;
}
/* Inserts a new Node at front of the list. */
function push(new_data) {
/*
* 1 & 2: Allocate the Node & Put in the data
*/
var new_node = new Node(new_data);
/* 3. Make next of new Node as head */
new_node.next = head;
/* 4. Move the head to point to new Node */
head = new_node;
}
/* Function to print linked list */
function printList(head) {
var temp = head;
while (temp != null) {
document.write(temp.data + " ");
temp = temp.next;
}
document.write("<br/>");
}
/* Driver program to test above functions */
/*
Constructed Linked List is
1->2->3->4->5->6-> 7->8->8->9->null
*/
push(-5);
push(5);
push(4);
push(3);
push(-2);
push(1);
push(0);
document.write("Original List :<br/>");
printList(head);
head = sortedList(head);
document.write("Sorted list :<br/>");
printList(head);
// This code contributed by aashish1995
</script>
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