×

Search anything:

# Move the first element of the linked list to the end Get this book -> Problems on Array: For Interviews and Competitive Programming

In this problem, given a linked list, we move the first element of the linked list to the end of the linked list.

``````Example input:
1 -> 2 -> 2 -> 3

Example output:
2 -> 2 -> 3 -> 1
``````

2. Brute Force
3. Solution Approach
4. Implementation of the approach
5. A small example to understand the solution

### What are linked lists ?

Linked List is a data structure. It is a linear data structure where the elements of the linked list are stored in non-consecutive
memory locations, each node in the linked list contains a data item and pointer to the next node in the linked list.

In our program we have represented a linked list using a `struct` construct in C++.

``````struct node {
int data;
struct node* next;
};
``````

Here, `data` represents the data value in the node and the `next` pointer represents the pointer to the next node in the list.

# Brute Force

In Brute Force approach, we swap the data values of two adjacent nodes one by one till the first node reaches the last position.

Steps:

STEP1: For each value i from 1 to N-1
STEP 1.1: Swap Node i and Node i+1

Pseudocode:

``````for i = 0 to N-1
swap(node(i), node(i+1))
``````

This approach has an O(N) time complexity. We can reduce the number of operations performed in the efficient approach though the Time Complexity will remain same.

# Solution Approach

In this solution approach we maintain two pointers. The algorithm is as follows:

STEP 1: Two pointers, the "first" pointer and the "last" pointer are maintained.
STEP 2: Both of them initially contain reference to the head.
STEP 3: We traverse the Linked List using "last" pointer and "last" pointer is made to point to the last node of the Linked List.
STEP 5: The next of the last pointer points to the previous head and it's "next" stores "null".

Pseudocode:

``````Node first = HEAD, last = HEAD;

while (last-> next != NULL)
last = last->next;

// Update last node
last->next = first;
``````

# Implementation of the approach

Here we have implemented the above approach in `C++`

``````#include <bits/stdc++.h>
using namespace std;

//node representation
struct node {
int data;
struct node* next;

};

//pointer declaration
struct node* tail = new node;
struct node* temp = new node;
struct node* curr;
struct node* pre;

//this is a function to print the data items in the linked list
while(temp != NULL){
cout << temp -> data << " ";
temp = temp -> next;
}
}

//the move to end function which implements the algorithm.

if(*head_pointer == NULL){ //this means our list is empty, we return
return;
}

//go to the last node of the list and
//store the address of the last node
while(last -> next != NULL){
last = last -> next;
}
//we store the address of the second node here, this is the new head.
//the previous head has the next set as NULL
first -> next = NULL;
//the previous head now becomes the tail
last -> next = first;
}

int main(){
int n, num, key;
cout << "Enter the number of elements" <<endl;
cin >> n ;

//accepting list from user
cout << "Enter the elements: " <<endl;
do {
cin >> num;
}
else{
//create and initialize a new node
struct node *new_node = new node;
new_node -> data = num;
new_node -> next = NULL;
tail -> next = new_node;
tail = new_node;
}
n = n - 1;
}while(n > 0);
cout << "List before moving" <<endl;
cout <<"\nList after moving" <<endl;
}

``````

# A small example to understand the solution

``````head           tail
1 -> 3 -> 2 -> 3
``````

Initially the `head_pointer` pointer would be storing the address of the `head` or the first element of the linked list.

The `first` and `last` pointers are also initialized.

``````    head      tail
1 -> 3 -> 2 -> 3
``````

The `head_pointer` then points to the next element after the `head`. We make the next of `head` as our new head now.

``````    head      tail
1 -> 3 -> 2 -> 3
``````

Now `tail` is moved to the first element and it's next stores `null`. The structure of the list now becomes as follows

``````head           tail
3 -> 2 -> 3 -> 1
``````

This is the required output.

Time complexity:

The time complexity of this approach is given by O(N), where, N is the number of nodes in the linked list. As we traverse all the N nodes in one pass, this is done to reach the `tail` pointer. The space complexity is O(1) as extra space is not allocated during this process.

#### Harshita Kanal

Intern at OpenGenus foundation. Loves Web, Frontend, React.

Move the first element of the linked list to the end