linklist
linklist
Linked List Singly Linked List

C Algorithm – Move last element to front of a given Linked List

C Algorithm - Move last element to front of a given Linked List - Linked List - Write a C function that moves last element to front in a given Singly

Write a C function that moves last element to front in a given Singly Linked List. For example, if the given Linked List is 1->2->3->4->5, then the function should change the list to 5->1->2->3->4.

Algorithm:
Traverse the list till last node. Use two pointers: one to store the address of last node and other for address of second last node. After the end of loop do following operations.
i) Make second last as last (secLast->next = NULL).
ii) Set next of last as head (last->next = *head_ref).
iii) Make last as head ( *head_ref = last)

C Programming:

/* C Program to move last element to front in a given linked list */
#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
   head of the linked list inside this function.*/
void moveToFront(struct node **head_ref)
{
    /* If linked list is empty, or it contains only one node,
      then nothing needs to be done, simply return */
    if (*head_ref == NULL || (*head_ref)->next == NULL)
        return;
 
    /* Initialize second last and last pointers */
    struct node *secLast = NULL;
    struct node *last = *head_ref;
 
    /*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 */
    last->next = *head_ref;
 
    /* Change the head pointer to point to last node now */
    *head_ref = last;
}
 
/* UTILITY FUNCTIONS */
/* Function to add a node at the begining 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 */
    new_node->next = (*head_ref);
 
    /* move the head to point to the new node */
    (*head_ref)    = 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;
    }
}
 
/* Druver 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;
}

Output:

 Linked list before moving last to front 
1 2 3 4 5 
 Linked list after removing last to front 
5 1 2 3

Time Complexity: O(n) where n is the number of nodes in the given Linked List.

READ  C Algorithm - Move last element to front of a given Linked List

About the author

Venkatesan Prabu

Venkatesan Prabu

Wikitechy Founder, Author, International Speaker, and Job Consultant. My role as the CEO of Wikitechy, I help businesses build their next generation digital platforms and help with their product innovation and growth strategy. I'm a frequent speaker at tech conferences and events.

Add Comment

Click here to post a comment