Linked lists are one of the most foundational data structures in computer science, and rearranging them can be a fun yet challenging task. One such problem is Reorder List, where you’re required to rearrange the elements of a singly linked list into a specific order. Let’s break this problem into its core components for a deeper understanding.
Understanding The Problem
You are given the head of a singly linked list, and your task is to rearrange its elements such that:
1. The first element is followed by the last element.
2. The second element is followed by the second-to-last element, and so on.
Additionally:
• You must modify the list in-place—no extra data structures like arrays or additional linked lists are allowed.
• The solution must be efficient, adhering to a time complexity of O(n) and a space complexity of O(1).
Example 1:
• Input: 1 -> 2 -> 3 -> 4
• Output: 1 -> 4 -> 2 -> 3
Example 2:
• Input: 1 -> 2 -> 3 -> 4 -> 5
• Output: 1 -> 5 -> 2 -> 4 -> 3
This problem combines several key concepts in linked list manipulation:
1. Traversal: You need to traverse the entire list efficiently.
2. Reversal: Reversing part of the list will be critical to achieving the desired order.
3. Merging: After splitting the list, you’ll merge two parts alternately to achieve the final arrangement.
The Naive Approach: Convert the List to an Array
The core idea is to use an array as an auxiliary data structure:
1. Traverse the list to extract all the nodes (or their values) into an array.
2. Rearrange the elements in the array to achieve the desired alternating order.
3. Rebuild the linked list using the reordered array.
This approach works because arrays allow random access, making it easy to manipulate the order of elements.
class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
this.next = null;
}
}
public class ReorderListNaive {
public void reorderList(ListNode head) {
if (head == null || head.next == null) return;
// Step 1: Store nodes in an array
List<ListNode> nodes = new ArrayList<>();
ListNode current = head;
while (current != null) {
nodes.add(current);
current = current.next;
}
// Step 2: Reorder the array elements
int i = 0, j = nodes.size() - 1;
while (i < j) {
nodes.get(i).next = nodes.get(j);
i++;
if (i == j) break;
nodes.get(j).next = nodes.get(i);
j--;
}
// Step 3: Terminate the reordered list
nodes.get(i).next = null;
}
}While this approach works and is easy to understand, it fails to meet the problem’s strict space requirements:
• Extra Space Usage:
• The array introduces O(n) space overhead to store nodes, making it inefficient for large lists.
• Rebuilding Overhead:
• Reconstructing the list adds unnecessary steps that could be avoided by directly modifying the list in-place.
Breaking Down the Optimized Algorithm
The optimized solution involves three key steps:
1. Find the middle of the list.
2. Reverse the second half of the list.
3. Merge the two halves alternately.
- Find the Middle of the List
The first step is to locate the middle node of the list. This is achieved using the slow and fast pointer technique:
• Slow Pointer: Moves one step at a time.
• Fast Pointer: Moves two steps at a time.
When the fast pointer reaches the end of the list, the slow pointer will be at the middle. This divides the list into two halves.
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}2. Reverse the Second Half
Once the middle of the list is identified, reverse the second half of the list. This transforms the latter part of the list into a format suitable for merging with the first half.
Steps to Reverse the List:
1. Initialize three pointers: prev (to store the reversed part), curr (to iterate), and next (to keep track of the next node).
2. Iteratively reverse the next pointer of each node until the list is fully reversed.
ListNode prev = null, curr = slow, next = null;
while (curr != null) {
next = curr.next; // Save the next node
curr.next = prev; // Reverse the link
prev = curr; // Move prev forward
curr = next; // Move curr forward
}3. Merge the Two Halves
Finally, merge the two halves alternately:
• Use two pointers: one pointing to the first half and the other to the reversed second half.
• Modify the next pointers to alternately link nodes from both halves.
Steps to Merge:
1. Use two pointers, first and second, initialized to the heads of the two halves.
2. Alternately link nodes from the two halves until one of the pointers reaches the end.
ListNode first = head, second = prev; // prev is the head of the reversed second half
while (second.next != null) {
ListNode temp1 = first.next, temp2 = second.next;
first.next = second; // Link first to second
second.next = temp1; // Link second to the next of first
first = temp1; // Move first forward
second = temp2; // Move second forward
}Complete Algorithm in Java
Here’s how all the steps come together in the complete solution:
class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
this.next = null;
}
}
public class ReorderList {
public void reorderList(ListNode head) {
if (head == null || head.next == null) return;
// Step 1: Find the middle of the list
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// Step 2: Reverse the second half of the list
ListNode prev = null, curr = slow, next = null;
while (curr != null) {
next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
// Step 3: Merge the two halves
ListNode first = head, second = prev;
while (second.next != null) {
ListNode temp1 = first.next, temp2 = second.next;
first.next = second;
second.next = temp1;
first = temp1;
second = temp2;
}
}
}Complexity Analysis
1. Time Complexity: O(n)
• Finding the middle: O(n) .
• Reversing the second half: O(n) .
• Merging the two halves: O(n) .
2. Space Complexity: O(1)
• Only a few pointers are used for traversal and merging, ensuring constant space usage.
Conclusion
The optimized algorithm for reordering a linked list is a beautiful example of how combining fundamental techniques (like finding the middle, reversing a list, and merging two lists) can lead to an efficient and elegant solution. This approach works in linear time with constant space, making it well-suited for real-world scenarios and interview challenges.
Mastering this algorithm not only helps with linked list manipulation but also builds intuition for tackling similar problems involving in-place reordering and traversal. 🚀
