Rearrange the given linked list such that it consists of alternating minimum-maximum elements

Problem Statement

In this problem, we are given a LinkedList (root node) and we are asked to rearrange it such that after rearrangement, it will contain alternating minimum and maximum elements in the following format:

  • The first element should be the minimum element.
  • The second element should be the maximum element.
  • The third element should be the next minimum and the fourth element should be the next maximum and so on.

Let’s see an example:
Input:

Output:

Problem Statement Understanding

Let’s first understand the problem statement with the help of examples.

If the given linked list is: head β†’12 β†’ 4 β†’ 5 β†’ 9 β†’ 10 β†’ 6.
We can form our output list having alternating minimum-maximum elements following the below steps.

  • As 4 is the minimum element so, it will be the first element in the resultant list.

    • Resultant list after this step: head β†’4
  • 12 is the maximum element so, it will be the second element in the resultant list.

    • Resultant list after this step: head β†’4 β†’ 12
  • 5 is the next minimum after 4 so, it is the third element.

    • Resultant list after this step: head β†’4 β†’ 12 β†’ 5
  • 10 is the next maximum after 12 so, it is the fourth element.

    • Resultant list after this step: head β†’4 β†’ 12 β†’ 5 β†’ 10
  • 6 is the next minimum after 5 so, it is the fifth element.

    • Resultant list after this step: head β†’4 β†’ 12 β†’ 5 β†’ 10 β†’ 6
  • 9 is the next maximum after 10 so, it is the sixth element.

    • Resultant list after this step: head β†’4 β†’ 12 β†’ 5 β†’ 10 β†’ 6 β†’ 9
  • Our final resultant linked list having alternating minimum-maximum elements will be: head β†’4 β†’ 12 β†’ 5 β†’ 10 β†’ 6 β†’ 9

Now I think from the above examples, the problem statement is clear. So let's see how we will approach it. Any Ideas?

  • If not, it's okay. We will see in the next section some helpful observations using which we will try to devise our algorithm.

Let’s move to the next section.

Helpful Observations

  1. If we sort the given list we get:

  2. If we reverse the sorted list after the middle element we get:

  3. The first half of the linked list from observation 2, which contains linked list sorted in ascending order.

  4. The second half of the linked list from observation 2, which contains linked list sorted in descending order.

Here, on careful observation we can see that our resultant list head β†’4 β†’ 12 β†’ 5 β†’ 10 β†’ 6 β†’ 9 is nothing but just a combination of the alternate nodes from the two lists in observations 3 and 4. So, we will use this observation to create our algorithm.

Approach and Algorithm

  • Sort the given list. Here, we will be using merge sort to sort the given list. You can sort the list using any sorting method you like.
  • Get the middle element using the tortoise and hare approach. The tortoise and hare approach is the efficient way to find the middle element of a list.
  • Reverse the list after the middle element and store it as a separate list.
  • Create a new empty list pointed by the result pointer.
  • Alternatively, add elements from the firstList and the reversedList starting with the firstList as we have to add in minimum and maximum order.
  • After adding all the elements from the firstList and the reversedList into the list pointed by the result. The result will contain the required list having alternating minimum-maximum elements.

Dry Run

Code Implementation

public class Prepbytes {
    static class Node {
        int data;
        Node next;

        Node() {
        };

        Node(int num) {
            data = num;
            next = null;
        }
    };

    public static Node rearrangeListToHaveMinMaxElements(Node head) {
        if (head == null) {
            return head;
        }
 	   if (head.next == null) {
            return head;
        }

        head = getSortedList(head);

        Node mid = getMidNode(head);
        Node secondList = mid.next;
        mid.next = null;

        Node reversedList = getReversedList(secondList);
        Node firstList = head;

        Node result = new Node();
        Node node = result;

        while (firstList != null || reversedList != null) {

            if (firstList != null) {
                node.next = firstList;
                node = node.next;
                firstList = firstList.next;
            }

            if (reversedList != null) {
                node.next = reversedList;
                node = node.next;
                reversedList = reversedList.next;
            }
        }

        return result.next;
    }

    public static Node getSortedList(Node node) {
        if (node == null || node.next == null) {
            return node;
        }

        Node mid = getMidNode(node);
        Node next = mid.next;
        mid.next = null;

        Node lista = getSortedList(node);
        Node listb = getSortedList(next);

        return merge(lista, listb);
    }

    public static Node merge(Node lista, Node listb) {
        if (lista == null && listb == null) {
            return null;
        }

        Node temp = new Node();
        Node mergedList = temp;
        
        while (lista != null && listb != null) {
            
            if (lista.data < listb.data) {
                temp.next = lista;
                lista = lista.next;
            } else {
                temp.next = listb;
                listb = listb.next;
            }

            temp = temp.next;
        }
        if (lista != null) {
            temp.next = lista;
        } 
   else {
            temp.next = listb;
        }

        return mergedList.next;
    }

    public static Node getMidNode(Node node) {
        Node slow = node;
        Node fast = node;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    public static Node getReversedList(Node node) {
        if (node == null || node.next == null) {
            return node;
        }

        Node prev = null;
        Node next = null;

        while (node != null) {
            next = node.next;
            node.next = prev;
            prev = node;
            node = next;
        }

        return prev;
    }

    public static void main(String[] args) {
        Node head = new Node(12);
        head.next = new Node(4);
        head.next.next = new Node(5);
        head.next.next.next = new Node(9);
        head.next.next.next.next = new Node(10);
        head.next.next.next.next.next = new Node(6);

        head = rearrangeListToHaveMinMaxElements(head);
        while (head != null) {
            System.out.print(head.data + " ");
            head = head.next;
        }
    }
}

Output

4 12 5 10 6 9

Time Complexity: O(n*logn), where n is the number of nodes.

  • O(n*logn) time is used to sort the list.
  • O(n) time is used to find the mid element.
  • O(n) time is used to reverse the list.
  • O(n) to create the resultant list from the first list and reversed list.
    Summing up we get O(nlogn + n + n + n) = O(nlogn).

So, in this blog, we have tried to explain how you can rearrange a given list such that it consists of alternating minimum-maximum elements in the most efficient way. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.

Previous post Sublist Search (Search a linked list in another list)
Next post Find pairs with given sum in Sorted Doubly Linked List

Leave a Reply

Your email address will not be published. Required fields are marked *