Move the first element to the end of the given list

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 problem, we are given a singly linked list. We have to move the first element of the linked list to the end of the list.

Problem Statement Understanding

Let’s try to understand the problem statement with the help of a few examples by referring some best sites to learn coding

Suppose the given list is 1 → 7 → 13 → 15.

  • According to the problem statement, we have to move the first element of the linked list to the end of the list.
  • So to move the first element to the end of the list, we will have to remove the first element from its position and make it the last element. If we move the first element to the end of the list, the resultant list will look like 7 → 13 → 15 → 1

Now let’s take another example, say if the given list is 3 → 5 → 8 → 10.

  • We will move the first element of the list to the end of the list such that our resultant list will look like 5 → 8 → 10 → 3

Explanation: As we can see, the first element of the list is moved to the end of the list.

Some more examples

Input

Output

Input

Output

This question is not a very complex one. Let us first think about what we will need to complete the required task.

  • We will need a pointer to the first node and,
  • Another pointer to the last node.
  • Now that we know that we need these two pointers, we can easily find them with the [help of list traversal](https://www.prepbytes.com/blog/linked-list/circular-linked-list-traversal/ "help of list traversal").

Let us have a glance at the approach.

Approach and Algorithm

Our approach will be simple:

  • Create two pointers, first and last. Both will initially point to the head.
  • Now, first will keep pointing to the head and with the help of a while loop, we will increment the last pointer till it reaches the end of the list.
  • Now, we will make head point to the next of first, as after the required task of moving the first node to the end of the list, the second node will become the new head.
  • After that, we will make the next of the last point to first, as now first is the new last node of the list.
  • In the end, we will make next of the first point to NULL, as it is now the last node of the list.
  • Finally, after the above steps, we will have successfully moved the first element of the linked list to the end of the list.

Dry Run

Code Implementation

#include 
#include 

struct Node {
    int data;
    struct Node* next;
};

void moveToEnd(struct Node** head)
{

    if (*head == NULL || (*head)->next == NULL)
        return;

    struct Node* first = *head;
    struct Node* last = *head;

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

    *head = first->next;
    
    last->next = first;
    first->next = NULL;

    
}

void push(struct Node** head, int new_data)
{
    struct Node* new_node = new Node;
    new_node->data = new_data;
    new_node->next = (*head);
    (*head) = new_node;
}

void printList(struct Node* node)
{
    while (node != NULL) {
        printf("%d ", node->data);
        node = node->next;
    }
}

int main()
{
    struct Node* start = NULL;

    push(&start, 15);
    push(&start, 13);
    push(&start, 7);
    push(&start, 1);
 
    printf("\n Linked list before end\n");
    printList(start);
 
    moveToEnd(&start);
 
    printf("\n Linked list after \n");
    printList(start);
 
    return 0;
}
public class Sol
{
static class Node
{
    int data;
    Node next;
};

static Node moveToEnd( Node head_ref)
{

    if (head_ref == null || (head_ref).next == null)
        return null;

    Node first = head_ref;
    Node last = head_ref;

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

    head_ref = first.next;
    
last.next = first;
    first.next = null;

    
    return head_ref;
}
 

static Node push( Node head_ref, int new_data)
{
    Node new_node = new Node();
    new_node.data = new_data;
    new_node.next = (head_ref);
    (head_ref) = new_node;
    return head_ref;
}

static void printList( Node node)
{
    while (node != null)
    {
        System.out.printf("%d ", node.data);
        node = node.next;
    }
}

public static void main(String args[])
{
    Node start = null;

    start = push(start, 15);
    start = push(start, 13);
    start = push(start, 7);

    start = push(start, 1);
 
    System.out.printf("\n Linked list before \n");
    printList(start);
 
    start = moveToEnd(start);
 
    System.out.printf("\n Linked list after \n");
    printList(start);
}
}

Output

Linked list before
1 7 13 15
Linked list after
7 13 15 1


Space Complexity: O(1), as only temporary variables are being created

So, in this article, we have tried to explain the most efficient approach to move the first element to the end of the given list. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.

Previous post Java.util.LinkedList.get(), getFirst() and getLast() in Java
Next post Compare two strings represented as linked lists

Leave a Reply

Your email address will not be published. Required fields are marked *