按照数组中出现元素的顺序对链表进行排序

2021年4月30日19:16:42 发表评论 828 次浏览

本文概述

给定一个大小为N的数组和一个链表, 链表中的元素将来自该数组, 但也可以重复, 按顺序对链表进行排序, 元素将出现在数组中。可以假定该数组覆盖了链表的所有元素。

arr [] =

按照数组中出现元素的顺序对链表进行排序1

list=

按照数组中出现元素的顺序对链表进行排序2

排序list=

按照数组中出现元素的顺序对链表进行排序3

首先，创建一个哈希表，在链表中存储元素的频率。然后，简单地遍历列表和arr[i]的每个元素检查频率在has表，并修改列表的数据arr[i]元素的频率，最后打印列表。

C ++

//Efficient CPP program to sort given list in order
//elements are appearing in an array
#include <bits/stdc++.h>
using namespace std;
  
//Linked list node
struct Node {
     int data;
     struct Node* next;
};
  
//function prototype for printing the list
void printList( struct Node*);
  
//Function to insert a node at the
//beginning of the linked list
void push( struct Node** head_ref, int new_data)
{
     struct Node* new_node = new Node;
     new_node -> data = new_data;
     new_node -> next = *head_ref;
     *head_ref = new_node;
}
  
//function to print the linked list
void printList( struct Node* head)
{
     while (head != NULL) {
         cout <<head -> data <<" -> " ;
         head = head -> next;
     }
}
  
//Function that sort list in order of apperaing
//elements in an array
void sortlist( int arr[], int N, struct Node* head)
{
     //Store frequencies of elements in a
     //hash table.
     unordered_map<int , int> hash;
     struct Node* temp = head;
     while (temp) {        
         hash[temp -> data]++;
         temp = temp -> next;
     }
  
     temp = head;
   
     //One by one put elements in lis according
     //to their appearance in array
     for ( int i = 0; i <N; i++) {        
  
         //Update 'frequency' nodes with value 
         //equal to arr[i]
         int frequency = hash[arr[i]];
         while (frequency--) {
  
             //Modify list data as element 
             //appear in an array
             temp -> data = arr[i];
             temp = temp -> next;
         }
     }
}
  
//Driver Code
int main()
{
     struct Node* head = NULL;
     int arr[] = { 5, 1, 3, 2, 8 };
     int N = sizeof (arr) /sizeof (arr[0]);
  
     //creating the linked list
     push(&head, 3);
     push(&head, 2);
     push(&head, 5);
     push(&head, 8);
     push(&head, 5);
     push(&head, 2);
     push(&head, 1);
  
     //Function call to sort the list in order
     //elements are apperaing in an array
     sortlist(arr, N, head);
  
     //print the modified linked list
     cout <<"Sorted List:" <<endl;
     printList(head);
     return 0;
}

Java

//Efficient JAVA program to sort given list in order
//elements are appearing in an array
import java.util.*;
  
class GFG
{
  
//Linked list node
static class Node
{
     int data;
     Node next;
};
  
//Function to insert a node at the
//beginning of the linked list
static Node push(Node head_ref, int new_data)
{
     Node new_node = new Node();
     new_node.data = new_data;
     new_node.next = head_ref;
     head_ref = new_node;
     return head_ref;
}
  
//function to print the linked list
static void printList(Node head)
{
     while (head != null )
     {
         System.out.print(head.data+ "->" );
         head = head.next;
     }
}
  
//Function that sort list in order of apperaing
//elements in an array
static void sortlist( int arr[], int N, Node head)
{
     //Store frequencies of elements in a
     //hash table.
     HashMap<Integer, Integer> hash = new HashMap<Integer, Integer>();
     Node temp = head;
     while (temp != null ) 
     { 
         if (hash.containsKey(temp.data))
             hash.put(temp.data, hash.get(temp.data) + 1 );
         else
             hash.put(temp.data, 1 );
         temp = temp.next;
     }
  
     temp = head;
  
     //One by one put elements in lis according
     //to their appearance in array
     for ( int i = 0 ; i <N; i++) 
     {     
  
         //Update 'frequency' nodes with value 
         //equal to arr[i]
         int frequency = hash.get(arr[i]);
         while (frequency--> 0 ) 
         {
  
             //Modify list data as element 
             //appear in an array
             temp.data = arr[i];
             temp = temp.next;
         }
     }
}
  
//Driver Code
public static void main(String[] args)
{
     Node head = null ;
     int arr[] = { 5 , 1 , 3 , 2 , 8 };
     int N = arr.length;
  
     //creating the linked list
     head = push(head, 3 );
     head = push(head, 2 );
     head = push(head, 5 );
     head = push(head, 8 );
     head = push(head, 5 );
     head = push(head, 2 );
     head = push(head, 1 );
  
     //Function call to sort the list in order
     //elements are apperaing in an array
     sortlist(arr, N, head);
  
     //print the modified linked list
     System.out.print( "Sorted List:" + "\n" );
     printList(head);
}
}
  
//This code is contributed by PrinciRaj1992

Python3

# Efficient Python3 program to sort given list in order
# elements are appearing in an array
  
# Linked list node
class Node:
     def __init__( self ):
         self .data = 0
         self . next = None
  
# Function to insert a node at the
# beginning of the linked list
def push( head_ref, new_data):
  
     new_node = Node()
     new_node.data = new_data
     new_node. next = head_ref
     head_ref = new_node
     return head_ref
  
# function to print the linked list
def printList( head):
  
     while (head ! = None ):
      
         print (head.data, end = "->" )
         head = head. next
      
# Function that sort list in order of apperaing
# elements in an array
def sortlist( arr, N, head):
  
     # Store frequencies of elements in a
     # hash table.
     hash = dict ()
     temp = head
     while (temp ! = None ) :
      
         hash [temp.data] = hash .get(temp.data, 0 ) + 1
         temp = temp. next
      
     temp = head
  
     # One by one put elements in lis according
     # to their appearance in array
     for i in range (N): 
          
         # Update 'frequency' nodes with value 
         # equal to arr[i]
         frequency = hash .get(arr[i], 0 )
          
         while (frequency> 0 ) :
          
             frequency = frequency - 1
             # Modify list data as element 
             # appear in an array
             temp.data = arr[i]
             temp = temp. next
          
# Driver Code
  
head = None
arr = [ 5 , 1 , 3 , 2 , 8 ]
N = len (arr)
  
# creating the linked list
head = push(head, 3 )
head = push(head, 2 )
head = push(head, 5 )
head = push(head, 8 )
head = push(head, 5 )
head = push(head, 2 )
head = push(head, 1 )
  
# Function call to sort the list in order
# elements are apperaing in an array
sortlist(arr, N, head)
  
# print the modified linked list
print ( "Sorted List:" )
printList(head)
  
  
# This code is contributed by Arnab Kundu

C#

//Efficient C# program to sort given list in order
//elements are appearing in an array
using System;
using System.Collections.Generic;
  
class GFG
{
  
//Linked list node
public class Node
{
     public int data;
     public Node next;
};
  
//Function to insert a node at the
//beginning of the linked list
static Node push(Node head_ref, int new_data)
{
     Node new_node = new Node();
     new_node.data = new_data;
     new_node.next = head_ref;
     head_ref = new_node;
     return head_ref;
}
  
//function to print the linked list
static void printList(Node head)
{
     while (head != null )
     {
         Console.Write(head.data + "->" );
         head = head.next;
     }
}
  
//Function that sort list in order of apperaing
//elements in an array
static void sortlist( int []arr, int N, Node head)
{
     //Store frequencies of elements in a
     //hash table.
     Dictionary<int , int> hash = new Dictionary<int , int>();
     Node temp = head;
     while (temp != null ) 
     { 
         if (hash.ContainsKey(temp.data))
             hash[temp.data] = hash[temp.data] + 1;
         else
             hash.Add(temp.data, 1);
         temp = temp.next;
     }
     temp = head;
  
     //One by one put elements in lis according
     //to their appearance in array
     for ( int i = 0; i <N; i++) 
     {     
  
         //Update 'frequency' nodes with value 
         //equal to arr[i]
         int frequency = hash[arr[i]];
         while (frequency-->0) 
         {
  
             //Modify list data as element 
             //appear in an array
             temp.data = arr[i];
             temp = temp.next;
         }
     }
}
  
//Driver Code
public static void Main(String[] args)
{
     Node head = null ;
     int []arr = { 5, 1, 3, 2, 8 };
     int N = arr.Length;
  
     //creating the linked list
     head = push(head, 3);
     head = push(head, 2);
     head = push(head, 5);
     head = push(head, 8);
     head = push(head, 5);
     head = push(head, 2);
     head = push(head, 1);
  
     //Function call to sort the list in order
     //elements are apperaing in an array
     sortlist(arr, N, head);
  
     //print the modified linked list
     Console.Write( "Sorted List:" + "\n" );
     printList(head);
}
}
  
//This code is contributed by 29AjayKumar

输出：

Sort list:
5 -> 5 -> 1 -> 3 -> 2 -> 2 -> 8
木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: