Move last element to front of a given linked list hackerrank
Do not miss this exclusive book on Binary Tree Problems. Get it now for free. Show We will explore recursive and iterative algorithm to Move Last Element of Linked List to Front. IntroductionA linked list is a collection of nodes where each node is connected to the next node through a pointer. The first node is called a head and if the list is empty then the value of head is NULL. Each node in a list consists of at least two parts:
RepresentationTypes of Linked Lists
ADVANTAGES OF LINKED LIST
DISADVANTAGES OF LINKED LIST
APPLICATIONS OF LINKED LIST
Now we will talk about the implementation with logical approach for how to move the last element of Linked List to first/front position . IMPLEMENTATIONALGORITHM Let's take an example : Algorithm (Theory approach step-by-step):
The pseudo code will be like this : void moveLastToFront(node **root) { node* prev = NULL; node* last = *root; while( last->next != NULL) { prev = ptr; prev = last->next; } prev->next = NULL; last->next = *root; *root = last; }Logical ApproachWe have to move last element of Linked List to front Example list {1,2,3,4} should be changed to {4,1,2,3} // A Linked List Node class Node { int data; Node next; Node(int data, Node next) { this.data = data; this.next = next; } } class Main { // Helper function to print a given linked list public static void printList(Node head) { Node ptr = head; while (ptr != null) { System.out.print(ptr.data + " > "); ptr = ptr.next; } System.out.println("null"); } // Function to move the last node to the front of a given linked list public static Node rearrange(Node head) { // proceed only when the list is valid if (head == null || head.next == null) return null; Node ptr = head; // move to the second last node while (ptr.next.next != null) { ptr = ptr.next; } // transform the list into a circular list ptr.next.next = head; // Fix head head = ptr.next; // break the chain ptr.next= null; return head; } public static void main(String[] args) { // input keys int[] keys = { 1, 2, 3, 4 }; Node head = null; for (int i = keys.length - 1; i >= 0; i--) { head = new Node(keys[i], head); } head = rearrange(head); printList(head); } } // A Linked List Node class Node { int data; Node next; Node(int data, Node next) { this.data = data; this.next = next; } } class Main { // Helper function to print a given linked list public static void printList(Node head) { Node ptr = head; while (ptr != null) { System.out.print(ptr.data + " > "); ptr = ptr.next; } System.out.println("null"); } // Recursive function to move the last node to the front of a given linked list public static Node rearrange(Node head, Node prev, Node curr) { // if the current node is the last if (curr.next == null) { // make its next point to the first node curr.next = head; // set its previous node to point to null prev.next = null; // return current reference (new head) return curr; } return rearrange(head, curr, curr.next); } // Function to move the last node to the front of a linked list public static Node rearrange(Node head) { // if the list contains at least two nodes if (head != null && head.next != null) { head = rearrange(head, null, head); } return head; } public static void main(String[] args) { // input keys int[] keys = { 1, 2, 3, 4 }; Node head = null; for (int i = keys.length - 1; i >= 0; i--) { head = new Node(keys[i], head); } head = rearrange(head); printList(head); } }
TIME COMPLEXITYGiven time complexity is O(n) where 'n' is number of nodes present in Linked List. Learn at OpenGenus IQ Sign up for FREE 3 months of Amazon Music. YOU MUST NOT MISS. |