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).
Java
/* Java Program to move last element to front in a given linked list */class LinkedList{ // Head of list Node head; // Linked list Node class Node { int data; Node next; Node(int d) { data = d; next = null; } } void moveToFront() { /* If linked list is empty or it contains only one node then simply return. */ if(head == null || head.next == null) return; /* Initialize second last and last pointers */ Node secLast = null; Node last = head; /* 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 the next of last as head last.next = head; // Change head to point to // last node. head = last; } // Utility functions /* Inserts a new Node at front of the list. */ public void push(int new_data) { /* 1 & 2: Allocate the Node & Put in the data*/ Node new_node = new Node(new_data); // 3. Make next of new Node as head new_node.next = head; // 4. Move the head to point to // new Node head = new_node; } // Function to print linked list void printList() { Node temp = head; while(temp != null) { System.out.print(temp.data + " "); temp = temp.next; } System.out.println(); } // Driver code public static void main(String args[]) { LinkedList llist = new LinkedList(); /* Constructed Linked List is 1->2->3->4->5->null */ llist.push(5); llist.push(4); llist.push(3); llist.push(2); llist.push(1); System.out.println( "Linked List before moving last to front "); llist.printList(); llist.moveToFront(); System.out.println( "Linked List after moving last to front "); llist.printList(); }}// This code is contributed by Rajat Mishra |
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.
Space Complexity: O(1) because using constant variables
Please refer complete article on Move last element to front of a given Linked List for more details!
