Rearrange a given Linked List in-place

Introduction

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

Problem Statement

In this question, we are given a singly linked list. We have to rearrange it in place, in which there are alternating first and last nodes. Let us have a look at the input and output to get a clearer understanding of the problem.

Problem Statement Understanding

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

Suppose the linked list is:

As we can see, It is of the form:

Now, we have to rearrange the list, so that it becomes of the form:

i.e. Alternating first and last elements.

will transform to

So, the final linked list after rearrangement will be:

If the given linked list is:

Then, after rearrangement, the linked list will transform to:

Now, I think it is clear from the examples what we have to do in this problem. This is an interesting question. We have to make use of list traversal to obtain the desired output. The traversal is not going to be a simple one. We are going to tweak it a bit.

Try to think how we can approach this problem, if you are not able to get an optimized approach no problem think of brute force, and then we will try to optimize it together.

Now, we will see brute force approach, as well as an efficient approach.

Approach and Algorithm (Brute Force)

This approach is going to be pretty simple. We are going to create a node current and point it to the head. Then, while the current node is not NULL, we will find the last node, delete it from the end, and insert it just after the current node. After this step, we will increment the current node by 2 places, as we have now successfully inserted the last node after the first node. This process will continue till we reach the end of the list.

Time Complexity - O(n²), as we have to do a nested traversal of the given list
Space Complexity - O(1), as only temporary variables are being created.

Approach and Algorithm (Vector rearranging method)

In this approach, we will copy all the elements of the list to a vector. Now, we will traverse through the vector up to its middle (l/2, where l is the length of the vector), and insert the ith node and the (n-i-1)^th node in the list (where this i starts from 0). By doing this, we are creating the alternating list that we require.

Time Complexity - O(N), as a single list traversal is required.
Space Complexity - O(N), the space required to create a vector of size N.

Approach and Algorithm (Linked List Splitting)

This is the most efficient solution. We are first going to divide the list into two halves. After the division, we will reverse the second half and then do an alternate merge of the first and second halves.

Let us have a glance at the algorithm.

Algorithm

• Find the middle of the list using the slow and fast pointer technique. We are using the slow and fast pointer technique because it is the most efficient technique to find the middle of a linked list. Both pointers will point to the head of the list initially. Now, the fast pointer makes two jumps, and the slow pointer will make one jump. When the fast pointer will reach the end, the slow pointer will be at the middle of the list.
• After finding the middle, split the list into two halves. Create two nodes, say, head1 and head2, head1 will point to head, and head2 will point to slow → next. Now, make slow → next will point to NULL. By doing this, the division of the list is successful.
• Reverse the second half of the linked list using the list reversal technique.
• Now, alternatively add elements from the first list and second list as long as either of them exists.
• In the end, assign the head of the new list to the head pointer.

Dry Run

Code Implementation

#include 
using namespace std;

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

Node* newNode(int key)
{
    Node* temp = new Node;
    temp->data = key;
    temp->next = NULL;
    return temp;
}

void reverselist(Node** head)
{

    Node *prev = NULL, *curr = *head, *next;
 
    while (curr) {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
 
    *head = prev;
}

void printlist(Node* head)
{
    while (head != NULL) {
        cout << head->data << " ";
        if (head->next)
            cout << "-> ";
        head = head->next;
    }
    cout << endl;
}

void rearrange(Node** head)
{

    Node *slow = *head, *fast = slow->next;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }

    Node* head1 = *head;
    Node* head2 = slow->next;
    slow->next = NULL;

    reverselist(&head2);

    *head = newNode(0); 
 
    Node* curr = *head;
    while (head1 || head2) {

        if (head1) {
            curr->next = head1;
            curr = curr->next;
            head1 = head1->next;
        }

        if (head2) {
            curr->next = head2;
            curr = curr->next;
            head2 = head2->next;
        }
    }

    *head = (*head)->next;
}

int main()
{
    Node* head = newNode(1);
    head->next = newNode(3);
    head->next->next = newNode(8);
    head->next->next->next = newNode(13);

    printlist(head); 
    rearrange(&head); 
    printlist(head);
    return  0;
}

Output

1 → 3 → 8 → 13
1 → 13 → 3 → 8

Time Complexity: O(n), as a list traversal is needed.

So, in this article, we have tried to explain the most efficient approach to rearrange a given linked list in place. This is an important problem when it comes to coding interviews. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes visit Linked List.