Given a Linked list of integers, the task is to find N largest elements in the Linked List.
Examples:
Input: [4, 5, 1, 2, 9], N = 2
Output: [9, 5]Input: [81, 52, 45, 10, 3, 2, 96], N = 3
Output: [ 96, 81, 52]
Method 1 : Brute Force
Approach: To solve the problem follow the below idea:
The idea is to Sort the Linked list using any sorting method and then traverse the list up to N
Follow the steps to solve the problem:
- Sort the given list using bubble sort.
- Traverse the list up to N values
- Print the values.
Below is the implementation for the above approach:
C++
// C++ program to sort Linked List// using Bubble Sort by swapping nodes#include <bits/stdc++.h>using namespace std;// Structure for a nodestruct Node { int data; struct Node* next;} Node;// Function to swap the nodesstruct Node* swap(struct Node* ptr1, struct Node* ptr2){ struct Node* tmp = ptr2->next; ptr2->next = ptr1; ptr1->next = tmp; return ptr2;}// Function to sort the listint bubbleSort(struct Node** head, int count){ struct Node** h; int i, j, swapped; for (i = 0; i <= count; i++) { h = head; swapped = 0; for (j = 0; j < count - i - 1; j++) { struct Node* p1 = *h; struct Node* p2 = p1->next; if (p1->data < p2->data) { // Update the link after swapping *h = swap(p1, p2); swapped = 1; } h = &(*h)->next; } // Break if the loop ended without // any swap if (swapped == 0) break; }}// Function to print the listvoid printNLargestInList(struct Node* n, int N){ for (int i = 0; i <= N - 1 && n != NULL; i++) { cout << n->data << " "; n = n->next; } cout << endl;}// Function to insert a struct Node// at the beginning of a linked listvoid insertAtTheBegin(struct Node** start_ref, int data){ struct Node* ptr1 = (struct Node*)malloc(sizeof(struct Node)); ptr1->data = data; ptr1->next = *start_ref; *start_ref = ptr1;}// Driver Codeint main(){ int arr[] = { 4, 5, 1, 2, 9 }, N = 2; int list_size, i; // Start with empty linked list */ struct Node* start = NULL; list_size = sizeof(arr) / sizeof(arr[0]); // Create linked list from the array arr[] for (i = list_size - 1; i >= 0; i--) insertAtTheBegin(&start, arr[i]); // sort the linked list bubbleSort(&start, list_size); // Print largest N elements of the list printNLargestInList(start, N); return 0;} |
Java
public class Main { public static void main(String[] args) { // Create a new linked list LinkedList linkedList = new LinkedList(); // Define an array of integers int[] arr = { 4, 5, 1, 2, 9 }; // Specify the value of N for printing N largest elements int N = 2; // Insert elements from the array into the linked list at the beginning for (int num : arr) { linkedList.insertAtBegin(num); } // Print the N largest elements in the linked list linkedList.printNLargest(N); }}// Node class represents a node in the linked listclass Node { public int data; // Data of the node public Node next; // Reference to the next node in the list // Constructor to initialize a node with given data public Node(int data) { this.data = data; this.next = null; }}// LinkedList class represents a linked listclass LinkedList { private Node head; // Reference to the first node in the list // Constructor to initialize an empty linked list public LinkedList() { head = null; } // Function to insert a Node at the beginning of the linked list public void insertAtBegin(int data) { // Create a new node with the given data Node newNode = new Node(data); // Set the next of the new node to the current head newNode.next = head; // Update the head to be the new node head = newNode; } // Function to print the N largest elements in the linked list public void printNLargest(int N) { // Sort the linked list in descending order using Bubble Sort bubbleSort(); // Initialize a pointer to the head of the list Node current = head; // Print the first N elements in the list for (int i = 0; i < N && current != null; i++) { System.out.print(current.data + " "); current = current.next; } System.out.println(); } // Function to sort the linked list using Bubble Sort private void bubbleSort() { // Check if the list is empty or has only one element if (head == null || head.next == null) return; boolean swapped; // Perform Bubble Sort do { Node prev = null; Node current = head; swapped = false; while (current.next != null) { // Compare adjacent nodes and swap if needed if (current.data < current.next.data) { Node temp = current.next; current.next = temp.next; temp.next = current; if (prev == null) head = temp; else prev.next = temp; prev = temp; swapped = true; } else { prev = current; current = current.next; } } } while (swapped); }} |
Python3
# Structure for a nodeclass Node: def __init__(self, data): self.data = data self.next = None# Function to swap the nodesdef swap(ptr1, ptr2): tmp = ptr2.next ptr2.next = ptr1 ptr1.next = tmp return ptr2# Function to sort the list in ascending order (smallest to largest)def bubbleSort(head, count): h = None i, j, swapped = 0, 0, 0 for i in range(count + 1): h = head swapped = 0 for j in range(count - i - 1): p1 = h p2 = p1.next # Check if p2 is None (end of the list) if p2 is None: break if p1.data > p2.data: # Modified to sort in ascending order # Update the link after swapping h = swap(p1, p2) swapped = 1 h = h.next # Break if the loop ended without any swap if swapped == 0: break# Function to print the listdef printNLargestInList(n, N): result = [] while n is not None: result.append(n.data) n = n.next # Sort the result list in ascending order result.sort() # Print the largest N elements of the list for i in range(-1, -N - 1, -1): if i >= -len(result): print(result[i], end=" ") print()# Function to insert a Node# at the beginning of a linked listdef insertAtTheBegin(start_ref, data): ptr1 = Node(data) ptr1.next = start_ref[0] start_ref[0] = ptr1# Driver Codeif __name__ == "__main__": arr = [4, 5, 1, 2, 9] N = 2 list_size = len(arr) # Start with an empty linked list start = [None] # Create linked list from the array arr[] for i in range(list_size - 1, -1, -1): insertAtTheBegin(start, arr[i]) # Sort the linked list in ascending order (smallest to largest) bubbleSort(start[0], list_size) # Print largest N elements of the list in ascending order printNLargestInList(start[0], N) |
C#
using System;class Node{ public int data; public Node next; public Node(int data) { this.data = data; this.next = null; }}class LinkedList{ private Node head; public LinkedList() { head = null; } // Function to insert a Node at the beginning of the linked list public void InsertAtBegin(int data) { Node newNode = new Node(data); newNode.next = head; head = newNode; } // Function to print the N largest elements in the linked list public void PrintNLargest(int N) { BubbleSort(); Node current = head; for (int i = 0; i < N && current != null; i++) { Console.Write(current.data + " "); current = current.next; } Console.WriteLine(); } // Function to sort the linked list using Bubble Sort private void BubbleSort() { if (head == null || head.next == null) return; bool swapped; do { Node prev = null; Node current = head; swapped = false; while (current.next != null) { if (current.data < current.next.data) { Node temp = current.next; current.next = temp.next; temp.next = current; if (prev == null) head = temp; else prev.next = temp; prev = temp; swapped = true; } else { prev = current; current = current.next; } } } while (swapped); }}class Program{ static void Main(string[] args) { LinkedList linkedList = new LinkedList(); int[] arr = { 4, 5, 1, 2, 9 }; int N = 2; foreach (int num in arr) { linkedList.InsertAtBegin(num); } linkedList.PrintNLargest(N); }} |
Javascript
// Structure for a nodeclass Node { constructor(data) { this.data = data; this.next = null; }}// Function to swap the nodesfunction swap(ptr1, ptr2) { let tmp = ptr2.next; ptr2.next = ptr1; ptr1.next = tmp; return ptr2;}// Function to sort the list in ascending order (smallest to largest)function bubbleSort(head, count) { let h = null; let i, j, swapped; for (i = 0; i <= count; i++) { h = head; swapped = 0; for (j = 0; j < count - i - 1; j++) { let p1 = h; let p2 = p1.next; // Check if p2 is null (end of the list) if (p2 === null) { break; } if (p1.data > p2.data) { // Modified to sort in ascending order // Update the link after swapping h = swap(p1, p2); swapped = 1; } h = h.next; } // Break if the loop ended without any swap if (swapped === 0) { break; } }}// Function to print the listfunction printNLargestInList(n, N) { let result = []; while (n !== null) { result.push(n.data); n = n.next; } // Sort the result array in ascending order result.sort((a, b) => a - b); // Print the largest N elements of the list for (let i = result.length - 1; i >= Math.max(result.length - N, 0); i--) { console.log(result[i]); }}// Function to insert a Node at the beginning of a linked listfunction insertAtTheBegin(start_ref, data) { let ptr1 = new Node(data); ptr1.next = start_ref[0]; start_ref[0] = ptr1;}// Driver Codelet arr = [4, 5, 1, 2, 9];let N = 2;let list_size = arr.length;// Start with an empty linked listlet start = [null];// Create linked list from the array arr[]for (let i = list_size - 1; i >= 0; i--) { insertAtTheBegin(start, arr[i]);}// Sort the linked list in ascending order (smallest to largest)bubbleSort(start[0], list_size);// Print largest N elements of the list in ascending orderprintNLargestInList(start[0], N); |
Output
9 5
Time complexity: O(N2)
Auxiliary space: O(1)
Method 2: Max Heap
Intuition
Store the elements of the linked list in a priority queue (max heap). Pop out the elements from the heap till N becomes 0 and add it to an array. Return the array as our answer.
Algorithm
- Create a max heap (priority queue) to store the elements of the linked list.
- Iterate through the linked list from head to end.
- For each element, insert the data into the heap.
- Initialize an empty vector to store our answer.
- Pop out N elements from the max-heap and add it to the vector or array.
- Return the array and print the answer.
Code
C++
// C++ code for the above approach#include <bits/stdc++.h>using namespace std;// Define a linked list node structureclass Node {public: int data; Node* next; Node(int data) { this->data = data; this->next = NULL; }};// Function to find N largest elementsvector<int> findNLargestElements(Node* head, int N){ // Create a max-heap priority_queue<int, vector<int> > pq; // Traverse the linked list and insert elements into the // maxHeap while (head != NULL) { pq.push(head->data); head = head->next; } // Pop N largest elements from the maxHeap vector<int> result; for (int i = 0; i < N; i++) { if (!pq.empty()) { result.push_back(pq.top()); pq.pop(); } } return result;}// Function to print a vectorvoid print(vector<int>& v){ for (int num : v) { cout << num << " "; } cout << endl;}// Define a function to insert a node at the beginning of// the linked listvoid insertAtTheBegin(Node** head, int data){ Node* newNode = new Node(data); newNode->next = *head; *head = newNode;}int main(){ int arr[] = { 81, 52, 45, 10, 3, 2, 96 }; int N = 3; int list_size = sizeof(arr) / sizeof(arr[0]); // Start with an empty linked list Node* start = nullptr; // Create a linked list from the array for (int i = list_size - 1; i >= 0; i--) { insertAtTheBegin(&start, arr[i]); } vector<int> result = findNLargestElements(start, N); cout << "Output: "; print(result); return 0;}// This code is contributed by Abhinav Mahajan (abhinav_m22) |
Java
import java.util.PriorityQueue;import java.util.Vector;// Define a linked list node structureclass Node { public int data; public Node next; public Node(int data) { this.data = data; this.next = null; }}public class Main { // Function to find N largest elements static Vector<Integer> findNLargestElements(Node head, int N) { // Create a max-heap PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a); // Traverse the linked list and insert elements into the maxHeap while (head != null) { pq.add(head.data); head = head.next; } // Pop N largest elements from the maxHeap Vector<Integer> result = new Vector<>(); for (int i = 0; i < N; i++) { if (!pq.isEmpty()) { result.add(pq.poll()); } } return result; } // Function to print a vector static void print(Vector<Integer> v) { for (int num : v) { System.out.print(num + " "); } System.out.println(); } // Function to insert a node at the beginning of the linked list static Node insertAtTheBegin(Node head, int data) { Node newNode = new Node(data); newNode.next = head; return newNode; } public static void main(String[] args) { int[] arr = { 81, 52, 45, 10, 3, 2, 96 }; int N = 3; int list_size = arr.length; // Start with an empty linked list Node start = null; // Create a linked list from the array for (int i = list_size - 1; i >= 0; i--) { start = insertAtTheBegin(start, arr[i]); } Vector<Integer> result = findNLargestElements(start, N); System.out.print("Output: "); print(result); }} |
Python3
import heapq# Define a linked list node classclass Node: def __init__(self, data): self.data = data self.next = None# Function to find N largest elementsdef find_n_largest_elements(head, N): # Create a max heap max_heap = [] # Traverse the linked list and insert elements into the max heap while head: heapq.heappush(max_heap, -head.data) head = head.next # Pop N largest elements from the max heap result = [] for i in range(N): if max_heap: result.append(-heapq.heappop(max_heap)) return result# Function to print a listdef print_list(lst): print(" ".join(map(str, lst)))# Function to insert a node at the beginning of the linked listdef insert_at_the_begin(head, data): new_node = Node(data) new_node.next = head return new_nodeif __name__ == "__main__": arr = [81, 52, 45, 10, 3, 2, 96] N = 3 # Start with an empty linked list start = None # Create a linked list from the array for i in range(len(arr) - 1, -1, -1): start = insert_at_the_begin(start, arr[i]) result = find_n_largest_elements(start, N) print("Output:", end=" ") print_list(result) |
C#
using System;using System.Collections.Generic;// Define a linked list node structurepublic class Node{ public int data; public Node next; public Node(int data) { this.data = data; this.next = null; }}public class Program{ // Function to find N largest elements public static List<int> FindNLargestElements(Node head, int N) { // Create a max-heap by implementing a min-heap with reversed ordering var pq = new PriorityQueue<int>((x, y) => y.CompareTo(x)); // Traverse the linked list and insert elements into the maxHeap while (head != null) { pq.Enqueue(head.data); head = head.next; } // Pop N largest elements from the maxHeap var result = new List<int>(); for (int i = 0; i < N; i++) { if (pq.Count > 0) { result.Add(pq.Dequeue()); } } return result; } // Function to print a list public static void Print(List<int> list) { foreach (var num in list) { Console.Write(num + " "); } Console.WriteLine(); } // Define a function to insert a node at the beginning of the linked list public static void InsertAtTheBegin(ref Node head, int data) { var newNode = new Node(data); newNode.next = head; head = newNode; } public static void Main() { int[] arr = { 81, 52, 45, 10, 3, 2, 96 }; int N = 3; Node start = null; // Create a linked list from the array for (int i = arr.Length - 1; i >= 0; i--) { InsertAtTheBegin(ref start, arr[i]); } var result = FindNLargestElements(start, N); Console.Write("Output: "); Print(result); }}// Implement a priority queue for the C# codepublic class PriorityQueue<T> where T : IComparable<T>{ private List<T> data; private Comparison<T> comparison; public PriorityQueue(Comparison<T> comparison) { this.data = new List<T>(); this.comparison = comparison; } public void Enqueue(T item) { data.Add(item); int childIndex = data.Count - 1; while (childIndex > 0) { int parentIndex = (childIndex - 1) / 2; if (comparison(data[childIndex], data[parentIndex]) >= 0) break; T tmp = data[childIndex]; data[childIndex] = data[parentIndex]; data[parentIndex] = tmp; childIndex = parentIndex; } } public T Dequeue() { int lastIndex = data.Count - 1; T frontItem = data[0]; data[0] = data[lastIndex]; data.RemoveAt(lastIndex--); int parentIndex = 0; while (true) { int leftChildIndex = parentIndex * 2 + 1; if (leftChildIndex > lastIndex) break; int rightChildIndex = leftChildIndex + 1; if (rightChildIndex <= lastIndex && comparison(data[rightChildIndex], data[leftChildIndex]) < 0) leftChildIndex = rightChildIndex; if (comparison(data[parentIndex], data[leftChildIndex]) <= 0) break; T tmp = data[parentIndex]; data[parentIndex] = data[leftChildIndex]; data[leftChildIndex] = tmp; parentIndex = leftChildIndex; } return frontItem; } public int Count { get { return data.Count; } }}// This code is contributed by shivamgupta310570 |
Output
Output: 96 81 52
Time Complexity: O(N*logN). To insert elements into the max-heap, it takes logN time. We insert N elements from the linked list to the heap, hence the overall time complexity is O(N*logN).
Space Complexity: O(N). We create a max-heap data structure due to which it requires O(N) space.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
