Reorder List: Alternate First and Last Nodes

58.9k
0

Given the head of a singly linked list having N nodes, reorder the list in the given pattern
L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2 ....

Modify the linked list in-place without changing node values. Linked list nodes must be rearranged by updating pointers.

Example 1

Input: head = [1, 2, 3, 4]

Output: [1, 4, 2, 3]

Explanation: First node remains at front, last node comes next, then second node, then third node.

Example 2

Input: head = [1, 2, 3, 4, 5]

Output: [1, 5, 2, 4, 3]

Explanation: Nodes from the start and end are placed alternately until the middle node becomes last.

Brute Force Approach

Since a singly linked list only allows forward traversal, we first store all nodes in an array. This gives direct access to nodes from both the beginning and the end.

After storing the nodes, we use two pointers: one starting from the front and one from the back. We connect nodes alternately: first node to last node, last node to second node, second node to second last node, and so on. Finally, we set the last node’s next pointer to NULL to avoid cycles.

Algorithm

  • Create an empty array and store all linked-list nodes in traversal order, as the array provides direct access to both the beginning and end of the list.

  • Initialize left at the first index and right at the last index, since the required arrangement alternates between nodes from both ends.

  • Connect the left node to the right node, as the next position in the reordered list should come from the end.

  • Connect the right node to the next left node, continuing the alternating pattern between the two ends.

  • Move left one step forward and right one step backward, as the next pair of nodes should come closer toward the center.

  • Continue until the pointers meet or cross, since all nodes have been placed in the required alternating order.

  • Set the final node's next pointer to NULL, as this marks the end of the reordered list and prevents an unwanted cycle.

Dry Run

reorder list

reorder list

Solution

#include <bits/stdc++.h>
using namespace std;
class ListNode {
public:
int data;
ListNode* next;
// Define linked list node.
ListNode(int value) {
data= value;
next = nullptr;
}
};
class Solution {
public:
// Reorder linked list using stack reconstruction.
void reorderList(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return;
}
// Store all nodes for back access.
vector<ListNode*> nodes;
ListNode* current = head;
while (current != nullptr) {
nodes.push_back(current);
current = current->next;
}
// Connect front and back nodes alternately.
int left = 0;
int right = (int)nodes.size() - 1;
while (left < right) {
nodes[left]->next = nodes[right];
left++;
if (left == right) {
break;
}
nodes[right]->next = nodes[left];
right--;
}
// End the reordered linked list.
nodes[left]->next = nullptr;
}
};
// Build linked list from values.
ListNode* buildList(vector<int>& values) {
ListNode dummy(0);
ListNode* tail = &dummy;
for (int value : values) {
tail->next = new ListNode(value);
tail = tail->next;
}
return dummy.next;
}
// Print linked list values.
void printList(ListNode* head) {
ListNode* current = head;
while (current != nullptr) {
cout << current->data;
current = current->next;
if (current != nullptr) {
cout << " ";
}
}
}
// Driver code.
int main() {
vector<int> values = {1, 2, 3, 4, 5};
ListNode* head = buildList(values);
Solution solution;
solution.reorderList(head);
printList(head);
return 0;
}

Complexity Analysis

Time Complexity: O(N), where N is the total number of nodes. We traverse the list to store all nodes and then traverse the array once to reorder them.

Space Complexity: O(N), where N is the number of nodes. The array stores pointers to all N nodes.

Optimal Approach

The required order alternates between nodes from the front and the back of the linked list. Since a singly linked list cannot be traversed backward, we first find the middle and reverse the second half. This brings the last nodes to the front, making them easy to access. Finally, we merge the first half and the reversed second half alternately to obtain the required order, all by modifying the existing links in-place.

Algorithm

  • Return head when the list is empty or contains only one node, as there are not enough nodes to form a different arrangement.

  • Use slow and fast pointers to find the node before the second half, since slow moving one step and fast moving two steps allows the midpoint to be located in a single traversal.

  • Detach the second half from the first half, as the two portions need to be processed independently before they can be merged alternately.

  • Reverse the detached second half using iterative pointer reversal, since reversing it makes the nodes originally at the end accessible from the front.

  • Initialize one pointer for the first half and another for the reversed second half, as the final order needs to alternate between these two sequences.

  • Merge nodes alternately from both halves by updating their next pointers, since each step should take one node from the front half followed by one node from the reversed half.

  • Continue until the reversed second half is fully merged, which ensures the nodes are arranged in the required front-back alternating order.

  • Ensure the final node points to NULL, as the reordered list must terminate without retaining any old connection.

Dry Run

Diagram 1
1 / 2

Diagram 1

Solution

#include <bits/stdc++.h>
using namespace std;
class ListNode {
public:
int data;
ListNode* next;
// Constructor for a linked list node.
ListNode(int value) {
data = value;
next = nullptr;
}
};
class Solution {
private:
// Function to find the last node of the first half.
ListNode* findMid(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
// Move slow by one step and fast by two steps.
// Slow stops at the end of the first half.
while (fast->next != nullptr &&
fast->next->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
// Function to reverse a linked list.
ListNode* reverseLL(ListNode* head) {
ListNode* previous = nullptr;
ListNode* current = head;
while (current != nullptr) {
// Store the next node before changing the link.
ListNode* nextNode = current->next;
// Reverse the current node's pointer.
current->next = previous;
// Move previous and current one step forward.
previous = current;
current = nextNode;
}
// Previous becomes the new head of the reversed list.
return previous;
}
// Function to merge the two halves alternately.
void mergeLists(ListNode* first, ListNode* second) {
while (second != nullptr) {
// Store the next nodes before modifying links.
ListNode* firstNext = first->next;
ListNode* secondNext = second->next;
// Insert the current second-half node after first.
first->next = second;
// Connect the inserted node to the remaining first half.
second->next = firstNext;
// Move both pointers to their next available nodes.
first = firstNext;
second = secondNext;
}
}
public:
// Function to reorder the linked list as
// first, last, second, second-last, and so on.
void reorderList(ListNode* head) {
// No reordering is required for zero or one node.
if (head == nullptr || head->next == nullptr) {
return;
}
// Find the final node of the first half.
ListNode* middle = findMid(head);
// Store the beginning of the second half.
ListNode* second = middle->next;
// Separate the first half from the second half.
middle->next = nullptr;
// Reverse the second half so the last node comes first.
second = reverseLL(second);
// Merge the first half and reversed second half alternately.
mergeLists(head, second);
}
};
// Function to build a linked list from the given values.
ListNode* buildList(vector<int>& values) {
// Dummy node simplifies linked list construction.
ListNode dummy(0);
ListNode* tail = &dummy;
for (int value : values) {
// Create and attach a new node.
tail->next = new ListNode(value);
// Move the tail to the newly added node.
tail = tail->next;
}
// Return the first actual node.
return dummy.next;
}
// Function to print the linked list.
void printList(ListNode* head) {
ListNode* current = head;

Complexity Analysis

Time Complexity: O(N), where N is the total number of nodes. Finding the middle, reversing the second half, and merging both halves each take linear time.
Space Complexity: O(1), as N is the number of nodes and only a constant number of pointer variables are used; no extra data structure depends on N.

Interview follow-up Questions

No. Pointer links must be updated while node values stay unchanged.

Linked List

Read Similar Blogs

Linked List

Swap Nodes in Pairs

Given the head of a singly linked list, swap every two adjacent nodes and return the modified head. Node values must stay inside the original nodes, so the task swaps node links inste...

59.8k
Linked List

Merge Two Sorted Linked Lists

Given heads of two sorted linked lists, merge both lists into one sorted linked list and return the head of the merged list. Every node stores an integer value and a pointer to the next node. The f...

114.6k
Linked List

Find pairs with given sum in Doubly Linked List

Given a sorted doubly linked list containing positive distinct integers and an integer target, find every pair of node values whose sum equals target. Return pairs in increasing order based on the...

101.5k
Comments0