Move the first element to the end of the given list

Last Updated on November 18, 2022 by Prepbytes

This blog will describe the efficient approach to move first node to last in linked list. The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Moving the first element of the linked list at the end position will help you to understand the linked list in detail. 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 To Move First Element To Last In Linked List

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.

Let us have a glance at the approach.

Approach and Algorithm To Move First Element To Last In Linked List

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 To Move First Element To Last In Linked List

Code Implementation To Move First Element To Last In Linked List

#include <stdio.h>
#include <stdlib.h>
 
/* Link list node */
struct Node {
    int data;
    struct Node* next;
};
 
/* function prototypes */
struct Node* SortedMerge(struct Node* a, struct Node* b);
void FrontBackSplit(struct Node* source,
                    struct Node** frontRef, struct Node** backRef);
 
/* sorts the linked list by changing next pointers (not data) */
void MergeSort(struct Node** headRef)
{
    struct Node* head = *headRef;
    struct Node* a;
    struct Node* b;
 
    /* Base case -- length 0 or 1 */
    if ((head == NULL) || (head->next == NULL)) {
        return;
    }
 
    /* Split head into 'a' and 'b' sublists */
    FrontBackSplit(head, &a, &b);
 
    /* Recursively sort the sublists */
    MergeSort(&a);
    MergeSort(&b);
 
    /* answer = merge the two sorted lists together */
    *headRef = SortedMerge(a, b);
}
 
/* See https:// www.geeksforgeeks.org/?p=3622 for details of this
function */
struct Node* SortedMerge(struct Node* a, struct Node* b)
{
    struct Node* result = NULL;
 
    /* Base cases */
    if (a == NULL)
        return (b);
    else if (b == NULL)
        return (a);
 
    /* Pick either a or b, and recur */
    if (a->data <= b->data) {
        result = a;
        result->next = SortedMerge(a->next, b);
    }
    else {
        result = b;
        result->next = SortedMerge(a, b->next);
    }
    return (result);
}
 
/* UTILITY FUNCTIONS */
/* Split the nodes of the given list into front and back halves,
    and return the two lists using the reference parameters.
    If the length is odd, the extra node should go in the front list.
    Uses the fast/slow pointer strategy. */
void FrontBackSplit(struct Node* source,
                    struct Node** frontRef, struct Node** backRef)
{
    struct Node* fast;
    struct Node* slow;
    slow = source;
    fast = source->next;
 
    /* Advance 'fast' two nodes, and advance 'slow' one node */
    while (fast != NULL) {
        fast = fast->next;
        if (fast != NULL) {
            slow = slow->next;
            fast = fast->next;
        }
    }
 
    /* 'slow' is before the midpoint in the list, so split it in two
    at that point. */
    *frontRef = source;
    *backRef = slow->next;
    slow->next = NULL;
}
 
/* Function to print nodes in a given linked list */
void printList(struct Node* node)
{
    while (node != NULL) {
        printf("%d ", node->data);
        node = node->next;
    }
}
 
/* Function to insert a node at the beginning of the 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 */
    new_node->next = (*head_ref);
 
    /* move the head to point to the new node */
    (*head_ref) = new_node;
}
 
/* Driver program to test above functions*/
int main()
{
    /* Start with the empty list */
    struct Node* res = NULL;
    struct Node* a = NULL;
 
    /* Let us create a unsorted linked lists to test the functions
Created lists shall be a: 2->3->20->5->10->15 */
    push(&a, 15);
    push(&a, 10);
    push(&a, 5);
    push(&a, 20);
    push(&a, 3);
    push(&a, 2);
 
    /* Sort the above created Linked List */
    MergeSort(&a);
 
    printf("Sorted Linked List is: \n");
    printList(a);
 
    getchar();
    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);
}
}

class Node:
    def __init__(self):
        self.data = 0
        self.next = None

def moveToEnd( head_ref) :

    if (head_ref == None or (head_ref).next == None) :
        return None

    first = head_ref
    last = head_ref

    while (last.next != None) :
    
        last = last.next
    
    head_ref = first.next
    first.next = None
    last.next = first
    return head_ref

def push( head_ref, new_data) :

    new_node = Node()
    new_node.data = new_data
    new_node.next = (head_ref)
    (head_ref) = new_node
    return head_ref

def printList(node) :

    while (node != None):
    
        print(node.data, end = " ")
        node = node.next
    

start = None

start = push(start, 5)
start = push(start, 4)
start = push(start, 3)
start = push(start, 2)
start = push(start, 1)

print("Linked list before moving first to end")
printList(start)

start = moveToEnd(start)

print("\nLinked list after moving first to end")
printList(start)

Output

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

Space Complexity To Move First Element To Last In Linked List: O(1), as only temporary variables are being created

This blog will describe the best approach To Move First Element To Last In Linked List. Linked List is a topic which is required for the technical interview. 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.

FAQ

1. Is the linked list LIFO or FIFO?


A singly-linked list may be LIFO (last-in-first-out) or FIFO (first-in-first-out). If the list is using the LIFO method, the nodes will be added to and deleted from the same end. If it’s using FIFO, nodes will be added to one end and deleted from the opposite end. Additionally, the linked list may be sorted.


2. How do you move to the end of a linked list?


A simple solution is to one by one find all occurrences of a given key in the linked list. For every found occurrence, insert it at the end. We do it till all occurrences of the given key are moved to the end.


3. What happens if the last node of the linked list carries the address of the first node in its address pointer field?


This variation of linked list is circular linked list, in which the last node in the list points to the first node of the list.