LinkedListProblem 8 of 36
Write a Program to Move the last element to Front in a Linked List
Move Last Element to Front in a Linked List
Problem Statement
Given a singly linked list, move the last element to the front of the list. The operation should be done in-place without using any extra space.
Example
Input: 1 -> 2 -> 3 -> 4 -> 5 -> null
Output: 5 -> 1 -> 2 -> 3 -> 4 -> null
Input: 1 -> 2 -> null
Output: 2 -> 1 -> null
Input: 1 -> null
Output: 1 -> null
Brute Force Approach (Two Pass)
Intuition
First, find the length of the list. Then traverse to the second-last node, detach the last node, and move it to the front. This requires two traversals.
Algorithm
- Find the length of the linked list
- Traverse to the (n-1)th node (second-last)
- Detach the last node
- Make the last node point to the old head
- Update head to the last node
Implementation
Complexity Analysis
- Time Complexity: O(n) - Two passes through the list
- Space Complexity: O(1) - Only using constant extra space
Optimal Approach (Single Pass)
Intuition
We can solve this in a single traversal by using two pointers. Traverse until we reach the last node while keeping track of the second-last node. Then simply adjust the pointers.
Algorithm
- Handle edge cases (empty list or single node)
- Traverse with two pointers: secondLast and last
- When last reaches the end:
- Set secondLast.next = null
- Set last.next = head
- Update head = last
- Return new head
Visualization
Initial: 1 -> 2 -> 3 -> 4 -> 5 -> null
↑ ↑
secondLast last
Step 1: secondLast.next = null
1 -> 2 -> 3 -> 4 5
↑ ↑
secondLast last
Step 2: last.next = head
5 -> 1 -> 2 -> 3 -> 4
Step 3: head = last
↑
head
Result: 5 -> 1 -> 2 -> 3 -> 4 -> null
Implementation
Complexity Analysis
- Time Complexity: O(n) - Single pass through the list
- Space Complexity: O(1) - Only using constant extra space
Variant: Move Kth Element from End to Front
A more general version where we move the kth element from the end to the front:
Key Takeaways
- The problem can be solved in a single pass by tracking two consecutive nodes
- Always handle edge cases: empty list, single node list
- The key insight is to find the second-last node to disconnect the last node
- Pointer manipulation order matters: disconnect first, then reconnect
- This is a building block for more complex linked list operations
- The variant (move kth from end) uses similar logic with position calculation