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

Table of Contents:

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

Basics of Linked List

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.

Representation of linked lists

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 4: The next element after the head is made the new head by moving the head reference to the next of current head.
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;

// Traverse Linked List
while (last-> next != NULL)
    last = last->next;
    
// Update head
HEAD = HEAD->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* head;
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
void print_data(struct node* head){
 temp = head;
 while(temp != NULL){
    cout << temp -> data << " ";
    temp = temp -> next;
 }
}

//the move to end function which implements the algorithm.
void move_to_end(struct node** head_pointer){

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

struct node* first = *head_pointer;
struct node* last = *head_pointer;

//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.
*head_pointer = first -> next;
//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;
 if(head == NULL){
    head = new node;
    head -> data = num;
    head -> next = NULL;
    tail = head;
 }
 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;
print_data(head);
//pass the reference of head
move_to_end(&head);
cout <<"\nList after moving" <<endl;
print_data(head);
}

A small example to understand the solution

Consider the linked list:

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.