Linked lists are one of the fundamental data structures in computer science. A common interview question (and practical exercise) is how to take the last node of a singly linked list and move it to the front.
Let’s walk through the logic, example code, and why this operation matters.
Understanding the Problem
A singly linked list is a sequence of nodes where each node points to the next one. The last node (called the tail) has a next pointer set to null.
The task is simple:
- Take the last node
- Place it at the beginning of the list
- Adjust the pointers so the list remains valid
Example:
Before → 10 → 20 → 30 → 40
After → 40 → 10 → 20 → 30
Step-by-Step Approach
- Traverse the list until you reach the second-to-last node.
- Keep a pointer to the last node.
- Break the link from the second-to-last node to the last node.
- Make the last node point to the current head.
- Update the head pointer to the last node.
Example Implementation in Python
Here’s a simple implementation:
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def push(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
self.head = new_node
def move_last_to_front(self):
if not self.head or not self.head.next:
return # List is empty or has only one node
second_last = None
last = self.head
# Traverse to the last node
while last.next:
second_last = last
last = last.next
# Adjust pointers
second_last.next = None
last.next = self.head
self.head = last
def print_list(self):
temp = self.head
while temp:
print(temp.data, end=" → ")
temp = temp.next
print("None")
# Example usage
llist = LinkedList()
for value in [10, 20, 30, 40]:
llist.push(value)
print("Original List:")
llist.print_list()
llist.move_last_to_front()
print("Modified List:")
llist.print_list()
Output
Original List:
40 → 30 → 20 → 10 → None
Modified List:
10 → 40 → 30 → 20 → None
Time Complexity
- Traversal: O(n), since we must reach the last node.
- Pointer changes: O(1).
- Overall: O(n).
This is efficient for a single pass through the list.
Why This Matters
This exercise teaches you to:
- Manipulate pointers safely
- Handle edge cases (empty lists, single-node lists)
- Think like an interviewer: break problems into steps and code defensively
Final Thoughts
Moving the last node to the front of a linked list is a classic linked list manipulation problem. While simple, it builds the foundation for tackling more advanced problems like reversing lists, rotating nodes, and merging sorted lists.
