Linked List: Given a linked list convert into peak list

Problem Statement:

You are given a LL with unique values, you need to convert into peak list.

A LL is called as peak list, where in all the nodes are peak nodes.

Peak nodes are the nodes that have greater value than the surrounding nodes.

Example:

Input: 1 -> 2 -> 3 -> 4 -> 5 -> 9
Output: 1 -> 3 -> 2 -> 5 -> 4 -> 9

Solution Explanation:

Solution is very simple.

Sort the array.

Then we need to make the elements at the even index as peak.

For that, we need to swap the node at even postion in the sorted LL.

Time Complexity: O(N*log N)
Space Complexity: O(1)

Code Solution

#include <iostream> 
using namespace std;

struct Node {
    int data;
    struct Node* next;

    Node(int x)
    {
        data = x;
        next = NULL;
    }
};

Node* merge(Node* firstNode, Node* secondNode)
{
    Node* merged = new Node(-1);
    Node* temp = new Node(-1);

    merged = temp;

    while (firstNode != NULL && secondNode != NULL) {

        if (firstNode->data <= secondNode->data) {
            temp->next = firstNode;
            firstNode = firstNode->next;
        }

        else {
            temp->next = secondNode;
            secondNode = secondNode->next;
        }
        temp = temp->next;
    }

    while (firstNode != NULL) {
        temp->next = firstNode;
        firstNode = firstNode->next;
        temp = temp->next;
    }

    while (secondNode != NULL) {
        temp->next = secondNode;
        secondNode = secondNode->next;
        temp = temp->next;
    }

    return merged->next;
}

// function to get middle element
Node* getMiddle(Node* head)
{
    Node* slow = head;
    Node* fast = head->next;

    while (!slow->next && (!fast && !fast->next)) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}


Node* MergeSort(Node* head)
{

    if (head->next == NULL) {
        return head;
    }

    Node* mid = new Node(-1);
    Node* head2 = new Node(-1);

    mid = getMiddle(head);
    
    head2 = mid->next;
    mid->next = NULL;

    Node* newHead
        = merge(MergeSort(head), MergeSort(head2));
    return newHead;
}

Node* solution(Node* head)
{

    int count = 1; //use this variable to check if the value is even or odd

    Node* temp = head;

    while (temp->next != NULL) {

        if (count % 2 == 0) {
            swap(temp->data, temp->next->data);
        }

        temp = temp->next;
        count++;
    }

    return head;
}

void printList(Node* node)
{
    while (node != NULL) {
        printf("%d ", node->data);
        node = node->next;
    }
    printf("\n");
}

int main()
{
    // Linked list
    Node* head = new Node(1);
    head->next = new Node(2);
    head->next->next = new Node(3);
    head->next->next->next = new Node(4);
    head->next->next->next->next = new Node(5);

    cout << "Given LL:";
    printList(head);

    MergeSort(head);

    cout << "Solution: ";
    solution(head);
    printList(head);

    return 0;
}

Output

Given LL:1 2 3 4 5 
Solution: 1 3 2 5 4