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 */ using System; class LinkedList { // Head of list Node head; // Linked list Node public class Node { public int data; public Node next; public 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 ) { Console.Write(temp.data+ " " ); temp = temp.next; } Console.WriteLine(); } // 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); Console.WriteLine( "Linked List before moving last to front " ); llist.printList(); llist.moveToFront(); Console.WriteLine( "Linked List after moving last to front " ); llist.printList(); } } // This code is contributed by Arnab Kundu |
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!