Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# Rearrange a given Linked List in-place

Last Updated on November 21, 2022 by Prepbytes

This article will help you to approach a linked list problem “Rearrange linked list in alternate last and first” This problem is discussing using illustrations, intuition, and code in C, C++, Java, and python which will make this problem easier for you to understand let us take a look to the problem statement of Rearrange linked list in alternate last and first.

## How to Rearrange Linked List in Alternate Last and First Place

In this problem, we are given a linked list, and we have to move the last node of the linked list to the very first and make it head or root.

Input:

Output (After moving the last element to the front of the linked list):

Let’s try to understand the problem by taking an example.

Initial Linked list = 7 → 5 → 3 → 1

• Once we have reached the last node of the linked list, we will make the previous node of the last node point to NULL and the next of the last node will point to the head node.
• Finally, we will make the node which we inserted at the front of the linked list the new head of the linked list.

After moving the last node to the front of the linked list, our linked list will look like:

Updated Linked list = 1 → 7 → 5 → 3.

Well, this is a very basic problem, and furthermore we will continue with the approach to solve the problem.

## Approach and Algorithm of Rearrange linked list in alternate last and first

The most naive idea is to traverse the list till the last node or end of the LinkedList. Use two node pointers last and secLast – last used to store the address of the last node and the secLast is used to store the address of the second last node. After the end of the loop, do the following operations.

• We have to make the second last as last (secLast->next = NULL).
• Next step is to change next of last as head (_last->next = *headref).
• The final step is to make last as the head (_*headref = last).

## Code Implementation of Rearrange linked list in alternate last and first

```#include<stdio.h>
#include<stdlib.h>

/* A linked list node */
struct Node
{
int data;
struct Node *next;
};

/* We are using a double pointer head_ref here because we change
{
/* If linked list is empty, or it contains only one node,
then nothing needs to be done, simply return */
return;

/* Initialize second last and last pointers */
struct Node *secLast = NULL;

/*After this loop secLast contains address of second last
node and last contains address of last node in Linked List */
while (last->next != NULL)
{
secLast = last;
last = last->next;
}

/* Set the next of second last as NULL */
secLast->next = NULL;

/* Set next of last as head node */

/* Change the head pointer to point to last node now */
}

/* UTILITY FUNCTIONS */
/* Function to add a node at the beginning of Linked List */
void push(struct Node** head_ref, int new_data)
{
/* allocate node */
struct Node* new_node =
(struct Node*) malloc(sizeof(struct Node));

/* put in the data  */
new_node->data  = new_data;

/* link the old list off the new node */

/* move the head to point to the new node */
}

/* Function to print nodes in a given linked list */
void printList(struct Node *node)
{
while(node != NULL)
{
printf("%d ", node->data);
node = node->next;
}
}

/* Driver program to test above function */
int main()
{
struct Node *start = NULL;

/* The constructed linked list is:
1->2->3->4->5 */
push(&start, 5);
push(&start, 4);
push(&start, 3);
push(&start, 2);
push(&start, 1);

printf("\n Linked list before moving last to front\n");
printList(start);

moveToFront(&start);

printf("\n Linked list after removing last to front\n");
printList(start);

return 0;
}

```
```#include <bits stdc++.h="">
using namespace std;
class Node
{
public:
int data;
Node *next;
};
{
return;
Node *secLast = NULL;
while (last->next != NULL)
{
secLast = last;
last = last->next;
}
secLast->next = NULL;
}
{
Node* new_node = new Node();
new_node->data = new_data;
}
void printList(Node *node)
{
while(node != NULL)
{
cout << node->data << " ";
node = node->next;
}
}
int main()
{
Node *start = NULL;
push(&start, 1);
push(&start, 3);
push(&start, 5);
push(&start, 7);
moveToFront(&start);
printList(start);
return 0;
}

```
```class MoveLast
{

class Node
{
int data;
Node next;
Node(int d) {data = d; next = null; }
}

void moveToFront()
{
return;

/* Initialize second last and last pointers */
Node secLast = null;

while (last.next != null)
{
secLast = last;
last = last.next;
}

secLast.next = null;
}
void push(int new_data)
{
Node new_node = new Node(new_data);
}
void printList()
{
while(temp != null)
{
System.out.print(temp.data+" ");
temp = temp.next;
}
System.out.println();
}
public static void main(String args[])
{
MoveLast llist = new MoveLast();

llist.push(5);
llist.push(4);
llist.push(3);
llist.push(2);
llist.push(1);

System.out.println("Linked List before moving last to front ");
llist.printList();

llist.moveToFront();

System.out.println("Linked List after moving last to front ");
llist.printList();
}
}
```
```class Node:
def __init__(self, data):
self.data = data
self.next = None

def __init__(self):

def push(self, data):
new_node = Node(data)

def printList(self):
while tmp is not None:
print(tmp.data, end=" ")
tmp = tmp.next
print()

def moveToFront(self):
sec_last = None

if not tmp or not tmp.next:
return

while tmp and tmp.next :
sec_last = tmp
tmp = tmp.next

sec_last.next = None

if __name__ == '__main__':

llist.push(1)
llist.push(3)
llist.push(5)
llist.push(7)
llist.moveToFront()
llist.printList()

```

Output 1 7 5 3

Time Complexity Of Rearrange linked list in alternate last and first: O(n), where n is the number of nodes in the given Linked List.

Space complexity of Rearrange linked list in alternate last and first: O(1), constant space complexity, as no extra space is used.

Conclusion