C Program For Moving Last Element To Front Of A Given Linked List
Write a function that moves the last element to the 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 the last node. Use two pointers: one to store the address of the last node and the other for the address of the second last node. After the end of the loop do the following operations.
- Make second last as last (secLast->next = NULL).
- Set next of last as head (last->next = *head_ref).
- Make last as head ( *head_ref = last).
C
// 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 // beginning 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 of 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; } } // Driver code 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 ( "Linked list before moving last to front" ); printList(start); moveToFront(&start); printf ( "Linked list after removing last to front" ); 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 4
Time Complexity: O(n) where n is the number of nodes in the given Linked List.
Auxiliary space: O(1) as it is using constant space
Please refer complete article on Move last element to front of a given Linked List for more details!
Contact Us