Python 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).
Python3
# Python3 code to move the last item # to front class Node: def __init__( self , data): self .data = data self . next = None class LinkedList: def __init__( self ): self .head = None # Function to add a node # at the beginning of Linked List def push( self , data): new_node = Node(data) new_node. next = self .head self .head = new_node # Function to print nodes in # a given linked list def printList( self ): tmp = self .head while tmp is not None : print (tmp.data, end = ", " ) tmp = tmp. next print () # Function to bring the last node # to the front def moveToFront( self ): tmp = self .head # To maintain the track of # the second last node sec_last = None # To check whether we have not # received the empty list or list # with a single node if not tmp or not tmp. next : return # Iterate till the end to get # the last and second last node while tmp and tmp. next : sec_last = tmp tmp = tmp. next # Point the next of the second # last node to None sec_last. next = None # Make the last node as the # first Node tmp. next = self .head self .head = tmp # Driver Code if __name__ = = '__main__' : llist = LinkedList() # Swap the 2 nodes llist.push( 5 ) llist.push( 4 ) llist.push( 3 ) llist.push( 2 ) llist.push( 1 ) print ( "Linked List before moving last to front " ) llist.printList() llist.moveToFront() print ( "Linked List after moving last to front " ) llist.printList() |
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!