#include <Arduino.h>
#include <stdlib.h>
#include <time.h>

struct Node {
  int data;
  Node* next;
};

// Function to create a random linked list of size n
Node* generateRandomList(int n) {
  Node* head = new Node();
  head->data = rand() % 100; // Random number between 0 and 99
  head->next = nullptr;
  
  Node* current = head;
  for (int i = 1; i < n; i++) {
    Node* newNode = new Node();
    newNode->data = rand() % 100; // Random number between 0 and 99
    newNode->next = nullptr;
    current->next = newNode;
    current = newNode;
  }
  return head;
}

// Function to print the linked list
void printList(Node* head) {
  Node* current = head;
  while (current != nullptr) {
    Serial.print(current->data);
    Serial.print(" ");
    current = current->next;
  }
  Serial.println();
}

// Function to sort the linked list using bubble sort
void bubbleSort(Node* head) {
  if (head == nullptr) return;

  Node* current;
  Node* nextNode;
  bool swapped;

  do {
    swapped = false;
    current = head;
    while (current->next != nullptr) {
      nextNode = current->next;
      if (current->data > nextNode->data) {
        // Swap data
        int temp = current->data;
        current->data = nextNode->data;
        nextNode->data = temp;
        swapped = true;
      }
      current = nextNode;
    }
  } while (swapped);
}

void setup() {
  Serial.begin(9600);
  while (!Serial); // Wait for Serial to initialize
  
  srand(time(nullptr)); // Seed the random number generator
  
  int n = 100; // Size of the linked list
  Node* head = generateRandomList(n);
  
  Serial.println("Original list:");
  printList(head);

  unsigned long startTime = millis(); // Record start time
  
  bubbleSort(head); // Sort the linked list using bubble sort
  
  unsigned long endTime = millis(); // Record end time
  
  Serial.println("Sorted list:");
  printList(head);
  
  unsigned long timeTaken = endTime - startTime;
  Serial.print("Time taken to sort: ");
  Serial.print(timeTaken);
  Serial.println(" ms");
}

void loop() {
  // No code here for now
}