246. Move the Last Element to the Front of a Linked List

A singly linked list has n node values. Move its last node to become the new first node (front), shifting every other node one position later while keeping their relative order, and print the resulting sequence.

Input: The first line contains an integer n. The second line contains n space-separated integers, the linked list's values in order. Output: Print the resulting sequence after moving the last node to the front, space-separated.

1 <= n <= 10^5

This is a specific instance of the more general 'Rotate a Linked List by N Nodes' problem, with n fixed at exactly (list length - 1) - recognizing the connection shows a deeper understanding of the broader rotation pattern.

Move a linked list's last node to become its new first node, shifting everyone else one position later. Brute force: Copy all values into an array, rearrange the array (move the last element to the front), and rebuild the list from scratch - this works but allocates entirely new nodes when the existing ones can simply be relinked. Optimised: Finding the second-to-last node (via a single walk) and relinking just THREE pointers (the last node's next, the new head reference, and the second-to-last node's next) achieves the rearrangement directly on the EXISTING nodes, with no new allocation.

Traverse the list exactly once using two pointers moving together, one step behind the other (prev trailing curr). By the time curr reaches the last node, prev is already sitting at the second-to-last node, so the relinking - prev.next = null, last.next = old head, head = last - can be done immediately without any second pass to re-locate that position. This is the tightest possible version of the pointer-relinking approach, doing the minimum single traversal necessary. Time: O(n) (single pass) Space: O(1) extra

First traverse the list once to find its length n and a reference to the last node. Then traverse it again, walking to the (n-2)th node - the current second-to-last node - and perform the relinking directly on the existing nodes: set that node's next to null (making it the new tail), point the former last node's next to the old head, and update the head reference to the former last node. This avoids allocating any new nodes or arrays, but needs two separate passes over the list to first measure it and then locate the relinking point. Time: O(n) (two passes) Space: O(1) extra

Traverse the original linked list once, copying every node's value into an array in order. Then construct the desired rotated sequence directly from the array - the last value first, followed by all the other values in their original relative order - and print it (or build a brand-new linked list of freshly allocated nodes from this array). This never touches the original list's pointers at all, trading extra memory for conceptual simplicity. Time: O(n) Space: O(n)

1. Walk to the SECOND-TO-LAST node (since you'll need to detach the last node from it). 2. Point the last node's next pointer to the OLD head. 3. Make the last node the NEW head, and set the second-to-last node's next pointer to null (it's now the new tail).

Time: O(n) - one walk to reach the second-to-last node. Space: O(1) extra space - just relinking existing pointers.

n = 1 (the list is unchanged), and n = 10^5 for performance.

Be ready to handle the single-node list edge case explicitly - moving a list's only node 'to the front' leaves it completely unchanged, since there's nothing else to shift.