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(n2), 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 <stdio.h>
#include <stdlib.h>
// Creating the structure for node
struct Node {
int data;
struct Node* next;
};
// Function to create newNode in a linkedlist
struct Node* newNode(int key)
{
struct Node* temp = malloc(sizeof(struct Node));
temp->data = key;
temp->next = NULL;
return temp;
}
// Function to print the list
void printlist(struct Node* head)
{
while (head) {
printf("%d ", head->data);
if (head->next)
printf("->");
head = head->next;
}
printf("\n");
}
// Function to rearrange
void rearrange(struct Node** head, struct Node* last)
{
if (!last)
return;
// Recursive call
rearrange(head, last->next);
// (*head)->next will be set to NULL
// after rearrangement.
// Need not do any operation further
// Just return here to come out of recursion
if (!(*head)->next)
return;
// Rearrange the list until both head
// and last meet or next to each other.
if ((*head) != last && (*head)->next != last) {
struct Node* tmp = (*head)->next;
(*head)->next = last;
last->next = tmp;
*head = tmp;
}
else {
if ((*head) != last)
*head = (*head)->next;
(*head)->next = NULL;
}
}
// Drivers Code
int main()
{
struct Node* head = newNode(1);
head->next = newNode(2);
head->next->next = newNode(3);
head->next->next->next = newNode(4);
head->next->next->next->next = newNode(5);
// Print original list
printlist(head);
struct Node* tmp = head;
// Modify the list
rearrange(&tmp, head);
// Print modified list
printlist(head);
return 0;
}
#include <bits stdc++.h>
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;
}
class Node
{
int data;
Node next;
Node(int key)
{
data = key;
next = null;
}
}
class Inplace
{
Node left = null;
// Function to print the list
void printlist(Node head)
{
while (head != null) {
System.out.print(head.data + " ");
if (head.next != null) {
System.out.print("->");
}
head = head.next;
}
System.out.println();
}
void rearrange(Node head)
{
if (head != null) {
left = head;
reorderListUtil(left);
}
}
void reorderListUtil(Node right)
{
if (right == null) {
return;
}
reorderListUtil(right.next);
// we set left = null, when we reach stop condition,
// so no processing required after that
if (left == null) {
return;
}
// Stop condition: odd case : left = right, even
// case : left.next = right
if (left != right && left.next != right) {
Node temp = left.next;
left.next = right;
right.next = temp;
left = temp;
}
else { // stop condition , set null to left nodes
if (left.next == right) {
left.next.next = null; // even case
left = null;
}
else {
left.next = null; // odd case
left = null;
}
}
}
public static void main(String[] args)
{
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);
Inplace i=new Inplace();
// Print original list
i.printlist(head);
// Modify the list
i.rearrange(head);
// Print modified list
i.printlist(head);
}
}
class Node:
def __init__(self, d):
self.data = d
self.next = None
def printlist(node):
if(node == None):
return
while(node != None):
print(node.data," -> ", end = "")
node = node.next
def reverselist(node):
prev = None
curr = node
next=None
while (curr != None):
next = curr.next
curr.next = prev
prev = curr
curr = next
node = prev
return node
def rearrange(node):
slow = node
fast = slow.next
while (fast != None and fast.next != None):
slow = slow.next
fast = fast.next.next
node1 = node
node2 = slow.next
slow.next = None
node2 = reverselist(node2)
node = Node(0)
curr = node
while (node1 != None or node2 != None):
if (node1 != None):
curr.next = node1
curr = curr.next
node1 = node1.next
if(node2 != None):
curr.next = node2
curr = curr.next
node2 = node2.next
node = node.next
head = None
head = Node(1)
head.next = Node(3)
head.next.next = Node(8)
head.next.next.next = Node(13)
printlist(head)
rearrange(head)
print()
printlist(head)
Output
1 → 3 → 8 → 13
1 → 13 → 3 → 8
Time Complexity: O(n), as a list traversal is needed.
[forminator_quiz id="3893"]
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.