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 node
struct Node {
    int data;
    struct Node* next;
} Node;
 
// Function to swap the nodes
struct 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 list
int 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 list
void 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 list
void 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 Code
int 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 list
class 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 list
class 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 node
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
 
# Function to swap the nodes
def 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 list
def 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 list
def insertAtTheBegin(start_ref, data):
    ptr1 = Node(data)
    ptr1.next = start_ref[0]
    start_ref[0] = ptr1
 
# Driver Code
if __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 node
class Node {
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}
 
// Function to swap the nodes
function 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 list
function 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 list
function insertAtTheBegin(start_ref, data) {
    let ptr1 = new Node(data);
    ptr1.next = start_ref[0];
    start_ref[0] = ptr1;
}
 
// Driver Code
let arr = [4, 5, 1, 2, 9];
let N = 2;
let list_size = arr.length;
 
// Start with an empty linked list
let 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 order
printNLargestInList(start[0], N);

Output

9 5

Time complexity: O(N²)
Auxiliary space: O(1)

C++

Java

Python3

C#

Javascript

find N largest elements from a Linked list

Similar Reads