Move first element to end of a given Linked List
Write a C function that moves first element to end 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 2->3->4->5->1.
Algorithm:
Traverse the list till last node. Use two pointers: one to store the address of last node(last) and other for address of first node(first). After the end of loop do following operations.
- Make head as second node (*head_ref = first->next).
- Set next of first as NULL (first->next = NULL).
- Set next of last as first ( last->next = first)
Steps to solve the problem:
1. check if *head_ref is equal to null or *head_ref ->next is null than return.
2. declare two node pointers first and second.
3. while last->next is not null:
* update last to last->next.
4. update *head_ref to first->next.
5. point first->next to null.
6. point last->next to first.
Implementation:
C++
/* C++ Program to move first element to end 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 moveToEnd( 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 first and last pointers */ struct Node* first = *head_ref; struct Node* last = *head_ref; /*After this loop last contains address of last node in Linked List */ while (last->next != NULL) { last = last->next; } /* Change the head pointer to point to second node now */ *head_ref = first->next; /* Set the next of first as NULL */ first->next = NULL; /* Set the next of last as first */ last->next = first; } /* UTILITY FUNCTIONS */ /* Function to add a node at the beginning of Linked List */ void push( struct Node** head_ref, int new_data) { struct Node* new_node = new Node; new_node->data = new_data; new_node->next = (*head_ref); (*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 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 first to end\n" ); printList(start); moveToEnd(&start); printf ( "\n Linked list after moving first to end\n" ); printList(start); return 0; } |
Java
/* Java Program to move first element to end in a given linked list */ class Sol { /* A linked list node */ static class Node { int data; Node next; }; /* We are using a double pointer head_ref here because we change head of the linked list inside this function.*/ static Node moveToEnd( 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 null ; /* Initialize first and last pointers */ Node first = head_ref; Node last = head_ref; /*After this loop last contains address of last node in Linked List */ while (last.next != null ) { last = last.next; } /* Change the head pointer to point to second node now */ head_ref = first.next; /* Set the next of first as null */ first.next = null ; /* Set the next of last as first */ last.next = first; return head_ref; } /* UTILITY FUNCTIONS */ /* Function to add a node at the beginning of Linked List */ static Node push( Node head_ref, int new_data) { Node new_node = new Node(); new_node.data = new_data; new_node.next = (head_ref); (head_ref) = new_node; return head_ref; } /* Function to print nodes in a given linked list */ static void printList( Node node) { while (node != null ) { System.out.printf( "%d " , node.data); node = node.next; } } /* Driver code */ public static void main(String args[]) { Node start = null ; /* The constructed linked list is: 1.2.3.4.5 */ start = push(start, 5 ); start = push(start, 4 ); start = push(start, 3 ); start = push(start, 2 ); start = push(start, 1 ); System.out.printf( "\n Linked list before moving first to end\n" ); printList(start); start = moveToEnd(start); System.out.printf( "\n Linked list after moving first to end\n" ); printList(start); } } // This code is contributed by Arnab Kundu |
Python3
# Python3 Program to move first element to end # in a given linked list # A linked list node class Node: def __init__( self ): self .data = 0 self . next = None # We are using a double pointer head_ref # here because we change head of the linked # list inside this function. def moveToEnd( head_ref) : # If linked list is empty, or it contains # only one node, then nothing needs to be # done, simply return if (head_ref = = None or (head_ref). next = = None ) : return None # Initialize first and last pointers first = head_ref last = head_ref # After this loop last contains address # of last node in Linked List while (last. next ! = None ) : last = last. next # Change the head pointer to point # to second node now head_ref = first. next # Set the next of first as None first. next = None # Set the next of last as first last. next = first return head_ref # UTILITY FUNCTIONS # Function to add a node at the beginning # of Linked List def push( head_ref, new_data) : new_node = Node() new_node.data = new_data new_node. next = (head_ref) (head_ref) = new_node return head_ref # Function to print nodes in a given linked list def printList(node) : while (node ! = None ): print (node.data, end = " " ) node = node. next # Driver code start = None # The constructed linked list is: #1.2.3.4.5 start = push(start, 5 ) start = push(start, 4 ) start = push(start, 3 ) start = push(start, 2 ) start = push(start, 1 ) print ( "\n Linked list before moving first to end" ) printList(start) start = moveToEnd(start) print ( "\n Linked list after moving first to end" ) printList(start) # This code is contributed by Arnab Kundu |
C#
/* C# Program to move first element to end in a given linked list */ using System; class GFG { /* A linked list node */ public class Node { public int data; public Node next; }; /* We are using a double pointer head_ref here because we change head of the linked list inside this function.*/ static Node moveToEnd( 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 null ; /* Initialize first and last pointers */ Node first = head_ref; Node last = head_ref; /*After this loop last contains address of last node in Linked List */ while (last.next != null ) { last = last.next; } /* Change the head pointer to point to second node now */ head_ref = first.next; /* Set the next of first as null */ first.next = null ; /* Set the next of last as first */ last.next = first; return head_ref; } /* UTILITY FUNCTIONS */ /* Function to add a node at the beginning of Linked List */ static Node push( Node head_ref, int new_data) { Node new_node = new Node(); new_node.data = new_data; new_node.next = (head_ref); (head_ref) = new_node; return head_ref; } /* Function to print nodes in a given linked list */ static void printList( Node node) { while (node != null ) { Console.Write( "{0} " , node.data); node = node.next; } } /* Driver code */ public static void Main(String []args) { Node start = null ; /* The constructed linked list is: 1.2.3.4.5 */ start = push(start, 5); start = push(start, 4); start = push(start, 3); start = push(start, 2); start = push(start, 1); Console.Write( "\n Linked list before moving first to end\n" ); printList(start); start = moveToEnd(start); Console.Write( "\n Linked list after moving first to end\n" ); printList(start); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // JavaScript program to move first element // to end in a given linked list /* A linked list node */ class Node { constructor() { this .data = 0; this .next = null ; } } /* We are using a double pointer head_ref here because we change head of the linked list inside this function.*/ function moveToEnd(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 null ; /* Initialize first and last pointers */ var first = head_ref; var last = head_ref; /*After this loop last contains address of last node in Linked List */ while (last.next != null ) { last = last.next; } /* Change the head pointer to point to second node now */ head_ref = first.next; /* Set the next of first as null */ first.next = null ; /* Set the next of last as first */ last.next = first; return head_ref; } /* UTILITY FUNCTIONS */ /* Function to add a node at the beginning of Linked List */ function push(head_ref, new_data) { var new_node = new Node(); new_node.data = new_data; new_node.next = head_ref; head_ref = new_node; return head_ref; } // Function to print nodes in // a given linked list function printList(node) { while (node != null ) { document.write(node.data + " " ); node = node.next; } } // Driver code var start = null ; // The constructed linked list is: // 1.2.3.4.5 start = push(start, 5); start = push(start, 4); start = push(start, 3); start = push(start, 2); start = push(start, 1); document.write( "Linked list before " + "moving first to end<br>" ); printList(start); start = moveToEnd(start); document.write( "<br> Linked list after moving " + "first to end<br>" ); printList(start); // This code is contributed by rdtank </script> |
Linked list before moving first to end 1 2 3 4 5 Linked list after moving first to end 2 3 4 5 1
Time Complexity: O(n) where n is the number of nodes in the given Linked List.
Auxiliary Space: O(1)
Method: Optimized Move First Element to End of Linked List
Steps:
- If the linked list is empty or has only one element, return the same linked list.
- Store the head node in a variable and set the head to the second node.
- Traverse the linked list until the last node.
- Set the next of the last node to the original head node.
- Set the next of the original head node to None.
- Return the modified linked list.
C++
#include <iostream> using namespace std; class Node { public : int data; Node* next; Node( int data) { this ->data = data; next = nullptr; } }; class LinkedList { public : Node* head; LinkedList() { head = nullptr; } void insert( int data) { Node* new_node = new Node(data); if (!head) { head = new_node; } else { Node* current_node = head; while (current_node->next) { current_node = current_node->next; } current_node->next = new_node; } } void display() { Node* current_node = head; while (current_node) { cout << current_node->data << " " ; current_node = current_node->next; } cout << endl; } Node* move_first_to_end() { if (!head || !head->next) { return head; } Node* old_head = head; head = head->next; Node* current_node = head; while (current_node->next) { current_node = current_node->next; } current_node->next = old_head; old_head->next = nullptr; return head; } }; int main() { LinkedList linked_list; linked_list.insert(1); linked_list.insert(2); linked_list.insert(3); linked_list.insert(4); linked_list.insert(5); cout << "Original Linked List: " ; linked_list.display(); linked_list.move_first_to_end(); cout << "Modified Linked List: " ; linked_list.display(); return 0; } //This code is contributed by Akash Jha |
Java
public class Main { public static void main(String[] args) { LinkedList linked_list = new LinkedList(); linked_list.insert( 1 ); linked_list.insert( 2 ); linked_list.insert( 3 ); linked_list.insert( 4 ); linked_list.insert( 5 ); System.out.print( "Original Linked List: " ); linked_list.display(); linked_list.move_first_to_end(); System.out.print( "Modified Linked List: " ); linked_list.display(); } private static class Node { public int data; public Node next; public Node( int data) { this .data = data; this .next = null ; } } private static class LinkedList { public Node head; public LinkedList() { this .head = null ; } public void insert( int data) { Node new_node = new Node(data); if ( this .head == null ) { this .head = new_node; } else { Node current_node = this .head; while (current_node.next != null ) { current_node = current_node.next; } current_node.next = new_node; } } public void display() { Node current_node = this .head; while (current_node != null ) { System.out.print(current_node.data + " " ); current_node = current_node.next; } System.out.println(); } public Node move_first_to_end() { if ( this .head == null || this .head.next == null ) { return this .head; } Node old_head = this .head; this .head = this .head.next; Node current_node = this .head; while (current_node.next != null ) { current_node = current_node.next; } current_node.next = old_head; old_head.next = null ; return this .head; } } } //This code is contributed by Akash Jha |
Python3
class Node: def __init__( self , data): self .data = data self . next = None class LinkedList: def __init__( self ): self .head = None def insert( self , data): new_node = Node(data) if not self .head: self .head = new_node else : current_node = self .head while current_node. next : current_node = current_node. next current_node. next = new_node def display( self ): current_node = self .head while current_node: print (current_node.data, end = ' ' ) current_node = current_node. next print () def move_first_to_end( self ): if not self .head or not self .head. next : return self .head old_head = self .head self .head = self .head. next current_node = self .head while current_node. next : current_node = current_node. next current_node. next = old_head old_head. next = None return self .head linked_list = LinkedList() linked_list.insert( 1 ) linked_list.insert( 2 ) linked_list.insert( 3 ) linked_list.insert( 4 ) linked_list.insert( 5 ) print ( "Original Linked List: " ) linked_list.display() linked_list.move_first_to_end() print ( "Modified Linked List: " ) linked_list.display() |
C#
using System; class Node { public int data; public Node next; public Node( int data) { this .data = data; next = null ; } } class LinkedList { public Node head; public LinkedList() { head = null ; } public void insert( int data) { Node new_node = new Node(data); if (head == null ) { head = new_node; } else { Node current_node = head; while (current_node.next != null ) { current_node = current_node.next; } current_node.next = new_node; } } public void display() { Node current_node = head; while (current_node != null ) { Console.Write(current_node.data + " " ); current_node = current_node.next; } Console.WriteLine(); } public Node move_first_to_end() { if (head == null || head.next == null ) { return head; } Node old_head = head; head = head.next; Node current_node = head; while (current_node.next != null ) { current_node = current_node.next; } current_node.next = old_head; old_head.next = null ; return head; } } class Program { static void Main( string [] args) { LinkedList linked_list = new LinkedList(); linked_list.insert(1); linked_list.insert(2); linked_list.insert(3); linked_list.insert(4); linked_list.insert(5); Console.Write( "Original Linked List: " ); linked_list.display(); linked_list.move_first_to_end(); Console.Write( "Modified Linked List: " ); linked_list.display(); Console.ReadLine(); } } //This code is contributed by Akash Jha |
Javascript
class Node { constructor(data) { this .data = data; this .next = null ; } } class LinkedList { constructor() { this .head = null ; } insert(data) { let new_node = new Node(data); if ( this .head == null ) { this .head = new_node; } else { let current_node = this .head; while (current_node.next != null ) { current_node = current_node.next; } current_node.next = new_node; } } display() { let current_node = this .head; while (current_node != null ) { console.log(current_node.data + " " ); current_node = current_node.next; } console.log(); } move_first_to_end() { if ( this .head == null || this .head.next == null ) { return this .head; } let old_head = this .head; this .head = this .head.next; let current_node = this .head; while (current_node.next != null ) { current_node = current_node.next; } current_node.next = old_head; old_head.next = null ; return this .head; } } let linked_list = new LinkedList(); linked_list.insert(1); linked_list.insert(2); linked_list.insert(3); linked_list.insert(4); linked_list.insert(5); console.log( "Original Linked List: " ); linked_list.display(); linked_list.move_first_to_end(); console.log( "Modified Linked List: " ); linked_list.display(); //This code is contributed by Akash Jha |
Original Linked List: 1 2 3 4 5 Modified Linked List: 2 3 4 5 1
Time complexity: O(n)
Auxiliary space: O(1)
Contact Us