Rearrange a Linked List in place

Introduction

Are you not able to shuffle and manipulate the pointers in a linked list? Or if you can solve all questions on linked lists? In either case, we have brought you another problem on linked lists, i.e., rearrange a linked list in place. We will help you approach this problem using illustrations, intuition, and some code in the C++ programming language, which will make the problem easier for you to understand.

Source: Link

The question discussed in this blog covers three crucial concepts:

1. Reversing a Linked List

2. Traversing a linked list and shuffling pointers

3. Some techniques to solve the Linked List problem like two pointer approach etc.

The problem statement is that we are given a linked list containing n nodes. Now we need to rearrange the linked in such a way that if the linked list initially looked like

Node₁ , Node₂ , …………….., Node_n-1 Node_n ; now it should look like

Node₁ , Node_n , Node₂ , Node_n-1 … .

So if you notice, we need to rearrange the linked list in such a way that after

Node_i the next node should be Node_n-i+1 where i != n-i+1.

Let’s Understand the problem by taking an example:

You are given the following linked list with N = 6 nodes.

Now let us walk you through the example:

We have to rearrange the linked list such that after Node_i the next node should be Nord_n-i+1 where i != n-i+1.

So we will put 6 after 1.

Now linked list will look like the following:

Now we will put 5 after 2,

Hence the linked list will look like the following:

Finally, we have to place 4 after 3, which is the case in the above illustration. Hence, we are done with rearranging the linked list.

I hope you got the essence of the question from the above example. If not, then no worries, we will discuss the approach here.

Recommended Topic, Floyds Algorithm And Rabin Karp Algorithm

Approach

Let’s look at the approach that comes to our mind first.

So what we need to do is for a node at a K distance from the right to be placed after the node at a K distance from the left.

So the approach becomes simple.

Find the node at the end of the linked list.
Put it after the current node and move on to the next node, after which we have to put the node at the end.
Repeat the same process above until the node to be placed after the current node is not the node itself.

(The connection of the list is maintained after rearranging the nodes so that we don’t lose the nodes).

Don’t worry about the time complexity here; we will have a look at it later on.

Now we can think of a PseudoCode.

PseudoCode

#Assuming there is a function reverse(root) that reverses the linked list

Algorithm
___________________________________________________________________
procedure rearrangeLinkedList(root):
___________________________________________________________________
1. if root is NIL or root.next is NIL do         #  simple case
2. return  
3. end if
4. currNode ← root       #  pointer to the Node where we’ll place ending Node 
5. endNode ← null        # pointer to keep track of ending node in LL
6.        while curNode is not same as endNode do
7.         endNode ← removeEndingNode(root)    # find, remove ending Node
8.           tempNode ← curNode.next   # store link to the current node’s next
9. curNode.next ← endNode     # place ending node after current Node
10.                endNode.next ← tempNode   # retain the connection of LL.
11. curNode ← curNode.next.next;  # move to next node in original LL
12. end while
13.end procedure
___________________________________________________________________

Source: Meme Creator

Explanation of the pseudocode given above:

The first line in the pseudo-code handles the trivial cases. Then we try to find the ending node of the linked list using the ‘removeEndingNode’ function and remove it from the end. Then we rearrange the pointers of the linked list to place the ending node removed at its correct position. This process repeats until we reach the terminating condition, i.e., the ending node is not the same as the current node.

Source: link

Code in C++

//C++ program to find minimum number of swaps
#include <iostream>
using namespace std;

// struct Node for storing nodes
// of a linked list
struct Node{
    int val;
    Node *next;
    Node(int data){
        this->val = data;
        this->next = nullptr;
    }
};

// function that returns the ending 
// node of a linked list and deletes it.
Node* removeEndingNode(Node* root){
    Node *temp = root;
    while(temp!=nullptr and temp->next!=nullptr and temp->next->next!=nullptr){
        temp = temp->next;
    }
    Node *node = temp->next;
    temp->next=nullptr;
    return node;
}

//function to rearrange the linked List
void rearrangeLL(Node* root){
    //trivial case
    if(root==nullptr or root->next==nullptr) return;    
    Node *curNode = root;   // pointer to the Node where we’ll place ending Node 
    Node *endNode;      //pointer to keep track of ending node in LL
    while(curNode->next!=nullptr and curNode!=endNode){
        endNode = removeEndingNode(root);   //find, remove ending Node
        Node *tempNode = curNode->next;  //store link to the current node’s next
        curNode->next = endNode ;  // place ending node after current Node
        endNode->next = tempNode  ; //retain the connection of LL.
        curNode = curNode->next->next;  //move to next node in original LL 
    }
}

//function to print the linked list
void printLL(Node* root){
    Node* temp = root;
    while(temp){
        cout<<temp->val<<" ";
        temp = temp->next;
    }
    cout<<'\n';
}

int main() {
int num_Nodes=5;
// creating a linked List consisting of 5 elements
Node *root = new Node(5);           // add Node 5
root->next = new Node(2);           // add Node 2
root->next->next = new Node(1);     // add Node 1
root->next->next->next = new Node(4); // add Node 4
root->next->next->next->next = new Node(3); // add Node 3
cout<<"The linked list before rearranging Linked List: ";
printLL(root);                      //print original list
cout<<"The linked list after rearranging Linked List: ";
rearrangeLL(root);
printLL(root);                      // print the list after reversing in groups of K
return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

The linked list before rearranging Linked List: 5 2 1 4 3 
The linked list after rearranging Linked List: 5 3 2 4 1

Time Complexity: O(n²)

Note that the above algorithm takes O(n²) time complexity because we traverse the linked list again in each iteration to delete the ending element and return it, which takes O(n) time. For n iterations, it will take O(n²) to rearrange the whole linked list using the above algorithm.

Space complexity: O(1), as we are using no extra auxiliary space.

It’s often said that humans are never satisfied with what they have. We want more and more and more.

Source: MemeCreator

But why should we be satisfied with the above algorithm having an O(n²) time complexity? Let's assume that we have a million nodes with us, and we know that a computer with basic requirements has a capacity of running ~ 10⁸ operations in a second.

If we run the above algorithm, it will take approximately 1000 seconds to execute, which is not desirable.

So, let's discuss how we can optimize the solution for the problem and rearrange a linked list in place.

Now the very first question is, where are we consuming time?

(Note: it’s imperative to understand and find the root cause of the problem before directly jumping on to its solution.)

Tip of advice: There are many ways we can optimize the solution, and we cannot generalize a particular way to find an optimal solution for a given problem. So let's think of the solution by finding out where we are doing repetitive work.

Once identified, you can think of any way/idea that does the same work efficiently. Whether working with techniques like sliding window, two pointers, manipulating pointers, sorting, dynamic programming, pre-computation, or data structures like trees, heaps, maps, help you optimize your solution. Try to write some relations and expressions or formulate your problem mathematically in a general way and analyze it, which will help you simplify things.

(NOTE: we haven’t discussed a method to solve a problem, these are only ideas that can help you optimize solutions)

Let’s come back to the problem: rearrange a linked list in place.

Check out this problem - Reverse Nodes In K Group

Approach to a Time-efficient Solution

Here to traverse the linked list, we first took its ending node, then removed it and rearranged the linked list.

So, if we denote the problem as given in the questions i.e.

We have to put Node_n-i+1 after Node_i where i is the index of the node and,

i != n-i+1 .

So we can store all nodes in a single traversal in an auxiliary array or a map, and then in another traversal, we can recreate the list using the same pointers in the original linked list.

This will turn out to be a better algorithm than the O(n²) algorithm.

But now we are using space which worsens the space complexity for us. Nevertheless, we are looking for a better solution than this algorithm.

Now let us make some observations that could help us modify the algorithm a bit.

Say we have a linked list.

Node₁ → Node₂ →.. Node _j → Node _j+1…→ Node _n-1 → Node _n

Note what we want is

Node₁ →Node _n →.Node ₂ → Node _n-1 → . → Node _mid → Node _mid+1

Did you notice something? If we see carefully that we will be able to append nodes at most after the node which is at the middle position and only when the linked list has even elements; otherwise, in the case of odd length lists, we will only be able to append the respective node at most after the mid-1 index node.

Note if we have the 2 sub linked lists separately i.e.

L1: Node₁ → Node₂ →...→ Node _mid-1 → Node _mid

L2: Node_mid+1 → Node_mid+2 →...→ Node _n-1 → Node _n

Did you get some idea how we can solve it by splitting the lists into 2 sub-lists?

If yes, great going, but if no, then no worries.

What we are trying to do is try to achieve the resultant placing of nodes by using the already used space and not using some extra auxiliary space.

If we reverse the sub-linked list 2, wouldn’t it be easy to traverse the linked list like we do using the two-pointer approach?

After reversal : L2: Node_n → Node_n-1 →...→ Node _mid+2 → Node _mid+1

We can append nodes at respective places, and our goal to optimize the space and time will be achieved.

Algorithm(space and time optimized)

Find the middle element (you can use the slow-fast pointer approach)
Then make 2 sub-lists out of a singly linked list split at the middle index
Say they are denoted as L1, L2. Reverse the sub-list L2.
Now place the nodes in the sub-list L1 from L2 by maintaining 2 pointers.

I guess the algorithm says it all. There’s no need for giving another pseudoCode because all the techniques are quite familiar to us. Hence we can jump onto the coding part now. (Don’t worry, the code part will be self-explanatory).

CODE IN C++(Space and Time Optimized)

//C++ program to find minimum number of swaps
#include <iostream>
using namespace std;

// struct Node for storing nodes
// of a linked list
struct Node{
    int val;
    Node *next;
    Node(int data){
        this->val = data;
        this->next = nullptr;
    }
};

// typical function to reverse the linked list
Node* reverseLL(Node* root){
    Node* prev = nullptr;
    Node* next = nullptr;
    Node* current = root;
        
    while(current != nullptr){
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
        
    return prev;
}

// function to rearrange the list
void rearrangeLL(Node* root) {
    // get mid of linked list using fast and slow pointer
    Node* slow = root, *fast = root;
        
    while(fast != nullptr and fast->next != nullptr and fast->next->next != nullptr ){
        slow = slow->next;          // move the slow pointer
        fast = fast->next->next;    // move the fast pointer
    }
        
    // splitting the list into 2 parts  
    Node* reversedSecondHalf = reverseLL(slow->next); // reversed second sub-list
    slow->next = nullptr; // mark first sub-list's ending node next to null 
    
    // Maintain 2 pointers to to now rearrange and reconnect the LL
    Node* firstHead = root;                 // pointer to root of sub-List 1
    Node* secondHead = reversedSecondHalf; // pointer to root of reversed sub-List 2
    
    // reconnecting the linked list by placing the nodes in 
    // sub-List 2
    while(secondHead != nullptr){
        Node* temp = firstHead->next;
        firstHead->next = secondHead;
        secondHead = temp;
        firstHead = firstHead->next;
    }
}

//function to print the linked list
void printLL(Node* root){
    Node* temp = root;
    while(temp){
        cout<<temp->val<<" ";
        temp = temp->next;
    }
    cout<<'\n';
}

int main() {
int num_Nodes=5;
// creating a linked List consisting of 5 elements
Node *root = new Node(5);           // add Node 5
root->next = new Node(2);           // add Node 2
root->next->next = new Node(1);     // add Node 1
root->next->next->next = new Node(4); // add Node 4
root->next->next->next->next = new Node(3); // add Node 3
cout<<"The linked list before rearranging Linked List: ";
printLL(root);                      //print original list
cout<<"The linked list after rearrangingLinked List: ";
rearrangeLL(root);
printLL(root);                      // print the list after reversing in groups of K
return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

The linked list before rearranging Linked List: 5 2 1 4 3 
The linked list after rearranging Linked List: 5 3 2 4 1

Time Complexity: O(n) because reversing and reconnecting or merging the sub-lists take O(n) time, respectively. Hence the time complexity is O(n).

Space complexity: O(1), as no extra auxiliary space is used.

Must Read Difference between ArrayList and LinkedList

Frequently Asked Questions

How do I return a linked list size?

There are many ways we can return a linked list’s size. The first way is to traverse the list and increment the size when each node is visited. This is an O(n) approach. But suppose we want to answer online queries, then manipulating the size while adding and deleting nodes will help answer each question to find the size of the list, which will be O(1).

How do you reverse a linked list in K groups?

Reversing a linked list in K groups can be done recursively and iteratively. For each group of k elements starting from the root node, the basic concept is to reverse the k group linked list and then move to the head of the next group of K elements if it exists in the linked list. Repeat the same process until it reaches termination.

How do you reorder a linked list?

Reordering a linked list can be done using many techniques such as slow-fast pointers, two-pointers, recursion, etc.

Why do we need a dummy node in the linked list?

A dummy node is needed to carry out the operations of the linked list. Since we need to manipulate pointers within the linked list, we might lose the actual linked list if we manipulate without using a dummy pointer.

Conclusion

This article taught us how to rearrange a linked list in place by approaching the problem using a brute force approach to the most optimal approach finally. We discussed their implementation using an iterative method using illustrations, through pseudocode and then using a proper code (the general way one should practice linked lists).

We hope you were able to take away critical techniques like reversing a linked list, reconnecting pointers using dummy variables, slow and fast pointer approach, a two-pointer approach which is often used in linked lists, and ways we should generally go about solving Linked List problems.

Now, we recommend you to practice problem sets based on Linked List to master your fundamentals. You can get a wide range of questions similar to rearrange a linked list in place on Coding Ninjas Studio.