Move last node to front in linked list

The problem revolves around manipulating a singly linked list. In particular, the task is to move the last node of the linked list to the front. A singly linked list is a linear data structure where each element (node) holds a value and a reference to the next element. The last node is the one whose "next" pointer points to NULL.

Problem Statement and Description

Given a singly linked list, we want to reorganize it such that the last node becomes the new head while maintaining the order of other nodes. For instance, if we have the linked list 1 → 2 → 3 → 4 → 5, the result should be 5 → 1 → 2 → 3 → 4.

Example

Let's take the example of the linked list: 1 → 2 → 3 → 4 → 5 → 6 → 7.

• Before Moving Last Node
  • Linked List: 1 → 2 → 3 → 4 → 5 → 6 → 7
  • Explanation: This is how the linked list looks before moving the last node to the front.
• After Moving Last Node
  • Linked List: 7 → 1 → 2 → 3 → 4 → 5 → 6
  • Explanation: The last node, which was 7, is now moved to the front while maintaining the order of other nodes.

Idea to Solve

1. Traverse the linked list to find the second-to-last node. This can be achieved by iterating until the next node's next pointer is not NULL.
2. Once the second-to-last node is found, adjust the pointers to move the last node to the front.
3. Update the new head and set the last node's next pointer to NULL to break the linked list.

Pseudocode

moveLastNode(ref):
    if ref.head is NULL or ref.head.next is NULL:
        return

    temp = ref.head
    while temp is not NULL and temp.next is not NULL and temp.next.next is not NULL:
        temp = temp.next
    
    temp.next.next = ref.head
    ref.head = temp.next
    temp.next = NULL

Algorithm Explanation

1. Check if the linked list is empty or contains only one node. In such cases, there's no need to move the last node to the front, so just return.
2. Initialize a temporary pointer temp to point to the head of the linked list.
3. Traverse the linked list using the temp pointer to find the second-to-last node. The loop condition checks for temp being not NULL and having at least two more nodes ahead.
4. After exiting the loop, the temp pointer will be pointing to the second-to-last node.
5. Adjust the pointers to move the last node to the front: Set the next pointer of the last node (previously the second-to-last node) to point to the head node.
6. Update the head of the linked list to the last node, making it the new head.
7. Set the next pointer of the second-to-last node (now the new last node) to NULL, effectively breaking the linked list.

Code Solution

1) Move last element to front of a given linked list in c 2) Move last element to front of a given linked list in c++ 3) Move last element to front of a given linked list in java 4) Move last element to front of a given linked list in c# 5) Move last element to front of a given linked list in php 6) Shift last node at the beginning of linked list in node js 7) Move last element to front of a given linked list in python 8) Move last element to front of a given linked list in ruby 9) Move last element to front of a given linked list in scala 10) Move last element to front of a given linked list in swift 11) Move last element to front of a given linked list in kotlin 12) Move last element to front of a given linked list in node js 13) Move last element to front of a given linked list in golang 14) Move last element to front of a given linked list in vb.net

Time Complexity

• The algorithm involves traversing the linked list to find the second-to-last node. This takes O(n) time, where n is the number of nodes in the linked list.
• The rest of the operations involve adjusting pointers, which are constant-time operations.
• Hence, the overall time complexity of the algorithm is O(n).