Rearrange a given linked list in-place

Rearrange a given linked list in-place. - GeeksforGeeks
Given a singly linked list L₀ -> L₁ -> … -> L_n-1 -> L_n. Rearrange the nodes in the list so that the new formed list is : L₀ -> L_n -> L₁ -> L_n-1 -> L₂ -> L_n-2 …

1) Find the middle point using tortoise and hare method.
2) Split the linked list in two halves using found middle point in step 1.
3) Reverse the second half.
4) Do alternate merge of first and second halves. 

    Node reverselist(Node node) {

        Node prev = null, curr = node, next;

        while (curr != null) {

            next = curr.next;

            curr.next = prev;

            prev = curr;

            curr = next;

        }

        node = prev;

        return node;

    }

  

    void rearrange(Node node) {

  

        // 1) Find the middle point using tortoise and hare method 

        Node slow = node, fast = slow.next;

        while (fast != null && fast.next != null) {

            slow = slow.next;

            fast = fast.next.next;

        }

  

        // 2) Split the linked list in two halves

        // node1, head of first half    1 -> 2 -> 3

        // node2, head of second half   4 -> 5

        Node node1 = node;

        Node node2 = slow.next;

        slow.next = null;

  

        // 3) Reverse the second half, i.e., 5 -> 4

        node2 = reverselist(node2);

  

        // 4) Merge alternate nodes

        node = new Node(0); // Assign dummy Node

  

        // curr is the pointer to this dummy Node, which will

        // be used to form the new list

        Node curr = node;

        while (node1 != null || node2 != null) {

  

            // First add the element from first list

            if (node1 != null) {

                curr.next = node1;

                curr = curr.next;

                node1 = node1.next;

            }

  

            // Then add the element from second list

            if (node2 != null) {

                curr.next = node2;

                curr = curr.next;

                node2 = node2.next;

            }

        }

  

        // Assign the head of the new list to head pointer

        node = node.next;

    }

X.
1. Take two pointers prev and curr, which hold the addresses of head and head-> next.
2. Compare their data and swap.
After that, a new linked list is formed.

// function for rearranging a linked list with high and low value.

void rearrange(Node *head)

{

    if(head == NULL) //Base case.

        return;

  

    // two pointer variable.

    Node *prev = head, *curr = head -> next;

      

    while(curr)

    {

        // swap function for swapping data.

        if(prev -> data > curr -> data)

        swap(prev -> data, curr -> data);

  

        // swap function for swapping data.

        if(curr -> next && curr -> next -> data > curr -> data)

            swap(curr -> next -> data , curr -> data);

  

        prev = curr -> next;

        if( !curr -> next)

            break;

        curr = curr -> next -> next;

    }

}

https://www.geeksforgeeks.org/rearrange-linked-list-alternate-first-last-element/

In this post a different Deque based solution is discussed.

1) Create an empty deque
2) Insert all element from the linked list to the deque
3) Insert the element back to the linked list from deque in alternate fashion i.e first then last and so on

void arrange(struct Node* head)

{

    struct Node* temp = head;

    deque<int> d; // defining a deque

  

    // push all the elemnts of linked list in to deque

    while (temp != NULL) {

        d.push_back(temp->data);

        temp = temp->next;

    }

  

    // Alternatively push the first and last elements

    // from deque to back to the linked list and pop

    int i = 0;

    temp = head;

    while (!d.empty()) {

        if (i % 2 == 0) {

            temp->data = d.front();

            d.pop_front();

        }

        else {

            temp->data = d.back(); 

            d.pop_back(); 

        }

        i++;

        temp = temp->next; // increse temp

    }

}

Read full article from Rearrange a given linked list in-place. - GeeksforGeeks