Move last element to Front on Linked list in Kotlin

To move the last element of a linked list to the front, you can follow these steps:

1. Traverse the linked list to find the last node.
2. Set the next pointer of the second-to-last node to null to remove the last node from its current position.
3. Set the next pointer of the last node to the current head of the linked list.
4. Set the head of the linked list to the last node.

Here’s an implementation of this algorithm in Kotlin:

class Node(var value: Int) {
    var next: Node? = null
}
fun moveLastToFront(head: Node?): Node? {
    // Return the original list if it's empty or has only one node
    if (head == null || head.next == null) {
        return head
    }
    var curr = head
    var prev: Node? = null
    // Traverse the list to find the last node and its previous node
    while (curr?.next != null) {
        prev = curr
        curr = curr.next
    }
    // Remove the last node from its current position
    prev?.next = null
    // Set the last node to the current head of the list
    curr?.next = head
    // Set the head of the list to the last node
    return curr
}
fun main() {
    // Create a linked list: 1 -> 2 -> 3 -> 4 -> 5
    val head = Node(1)
    head.next = Node(2)
    head.next?.next = Node(3)
    head.next?.next?.next = Node(4)
    head.next?.next?.next?.next = Node(5)
    // Print the original linked list
    printLinkedList(head)
    // Move the last node to the front
    val newHead = moveLastToFront(head)
    // Print the modified linked list
    printLinkedList(newHead)
}
fun printLinkedList(head: Node?) {
    var curr = head
    while (curr != null) {
        print("${curr.value} ")
        curr = curr.next
    }
    println()
}

Step-by-step explanation of the moveLastToFront function:

1. The function takes a linked list head as input and returns the modified linked list.
2. If the linked list is empty or has only one node, we don’t need to do anything. In this case, we simply return the original list.
3. We initialize a variable curr to the head of the linked list. This variable will be used to traverse the linked list to find the last node.
4. We start traversing the linked list from the head and move forward until we reach the last node. We keep track of the previous node using a variable prev. We also update the curr variable at each iteration to move forward in the list.
5. After the traversal is complete, curr will point to the last node in the list, and prev will point to the second-to-last node. We remove the last node from its current position by setting the next pointer of prev to null.
6. We then set the next pointer of curr to the current head of the list. This makes the last node the new head of the list.
7. Finally, we return the new head of the list.

The time complexity of the moveLastToFront function is O(n), where n is the number of nodes in the linked list. This is because we need to traverse the linked list once to find the last node, and this operation takes linear time in the size of the list.

The space complexity of the function is O(1), because we only use a constant amount of additional memory to store the curr and prev variables, regardless of the size of the input list. Therefore, the space used by the function does not depend on the size of the list, and it is considered constant.