LeetCode Meditations: Reorder List
Let's start with the description for Reorder List:
You are given the head of a singly linked-list. The list can be represented as:
L0 → L1 → … → Ln - 1 → LnReorder the list to be on the following form:
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …You may not modify the values in the list's nodes. Only nodes themselves may be changed.
For example:
My initial solution was to get every node inside an array first, then link each value to the linked list in an alternating order.
Adding the values to an array is easy:
let nums = [];
let current = head;
while (current !== null) {
nums.push(current.val);
current = current.next;
}
let nums = [];
let current = head;
while (current !== null) {
nums.push(current.val);
current = current.next;
}
Then, we can point our current pointer back to the head node, and slice nums to start from the second element (since current is already pointing to the first element). That's also easy:
current = head;
nums = nums.slice(1);
current = head;
nums = nums.slice(1);
Then, we can use the Two Pointers technique to link the elements in an alternating fashion. We can also keep a flag variable to know which direction (left or right) to go next.
Since we're already pointing to the first element, we need to add the next item from the reversed portion (going left), so we can initialize this variable as false:
let goRight = false;
let goRight = false;
Then, as we update our left and right pointers, we can link our newly created ListNode, and flip the goRight flag accordingly.
Overall, it looks like this:
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val === undefined ? 0 : val)
* this.next = (next === undefined ? null : next)
* }
* }
*/
/**
Do not return anything, modify head in-place instead.
*/
function reorderList(head: ListNode | null): void {
let nums = [];
let current = head;
while (current !== null) {
nums.push(current.val);
current = current.next;
}
current = head;
nums = nums.slice(1);
let left = 0;
let right = nums.length - 1;
let goRight = false;
while (left <= right) {
if (goRight) {
current.next = new ListNode(nums[left++]);
goRight = false;
} else {
current.next = new ListNode(nums[right--]);
goRight = true;
}
current = current.next;
}
};
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val === undefined ? 0 : val)
* this.next = (next === undefined ? null : next)
* }
* }
*/
/**
Do not return anything, modify head in-place instead.
*/
function reorderList(head: ListNode | null): void {
let nums = [];
let current = head;
while (current !== null) {
nums.push(current.val);
current = current.next;
}
current = head;
nums = nums.slice(1);
let left = 0;
let right = nums.length - 1;
let goRight = false;
while (left <= right) {
if (goRight) {
current.next = new ListNode(nums[left++]);
goRight = false;
} else {
current.next = new ListNode(nums[right--]);
goRight = true;
}
current = current.next;
}
};
Time and space complexity
Adding each value to an array is an operation since we visit every node in the linked list. Then, we'll traverse this array again to convert it back to a linked list — another operation. Therefore, the time complexity of the overall function ends up being . The space complexity is also because of the array we create to store the values.
There is another way to solve this problem, as shown by NeetCode.
In this version, we'll make use of the Fast and Slow Pointers technique, where we initialize two pointers: fast and slow. slow will initially point to the head, while fast will point to head.next, and we'll update them until fast (or its next pointer) reaches the end, at which point slow stays at the middle node.
let slow = head;
let fast = head.next;
while (fast !== null && fast.next !== null) {
slow = slow.next;
fast = fast.next.next;
}
let slow = head;
let fast = head.next;
while (fast !== null && fast.next !== null) {
slow = slow.next;
fast = fast.next.next;
}
Now that slow is at the middle node, we can partition the list into two.
However, we need to go through the second half in reverse order. So, we can get the head of this second half (which is slow.next), and point its next pointer to null.
let second = slow.next;
slow.next = null;
let second = slow.next;
slow.next = null;
Then, we'll just iterate in reverse order. If you remember from Reverse Linked List, this is how we're going to do it:
let prevNode = null;
while (second !== null) {
let nextNode = second.next;
second.next = prevNode;
prevNode = second;
second = nextNode;
}
let prevNode = null;
while (second !== null) {
let nextNode = second.next;
second.next = prevNode;
prevNode = second;
second = nextNode;
}
Now that the second portion is reversed, we can go ahead and do the main job of merging all the nodes.
After this reversing operation, the prevNode is now at the last node of the list (because second points to null). Now, we'll alternate pointers: pointing left's next to the right, and right's next to the left one.
let left = head;
let right = prevNode;
while (right !== null) {
let nextLeft = left.next;
let nextRight = right.next;
// Rearrange pointers alternatively
left.next = right;
right.next = nextLeft;
// Update pointers
left = nextLeft;
right = nextRight;
}
let left = head;
let right = prevNode;
while (right !== null) {
let nextLeft = left.next;
let nextRight = right.next;
// Rearrange pointers alternatively
left.next = right;
right.next = nextLeft;
// Update pointers
left = nextLeft;
right = nextRight;
}
All in all, the function will look like this:
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val === undefined ? 0 : val)
* this.next = (next === undefined ? null : next)
* }
* }
*/
/**
Do not return anything, modify head in-place instead.
*/
function reorderList(head: ListNode | null): void {
// Get to the middle node
let slow = head;
let fast = head.next;
while (fast !== null && fast.next !== null) {
slow = slow.next;
fast = fast.next.next;
}
// Get the head of the second half of the list
let second = slow.next;
slow.next = null;
// Reverse the second half of the list
let prevNode = null;
while (second !== null) {
let nextNode = second.next;
second.next = prevNode;
prevNode = second;
second = nextNode;
}
let left = head;
let right = prevNode;
while (right !== null) {
let nextLeft = left.next;
let nextRight = right.next;
// Rearrange pointers alternatively
left.next = right;
right.next = nextLeft;
// Update pointers
left = nextLeft;
right = nextRight;
}
};
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val === undefined ? 0 : val)
* this.next = (next === undefined ? null : next)
* }
* }
*/
/**
Do not return anything, modify head in-place instead.
*/
function reorderList(head: ListNode | null): void {
// Get to the middle node
let slow = head;
let fast = head.next;
while (fast !== null && fast.next !== null) {
slow = slow.next;
fast = fast.next.next;
}
// Get the head of the second half of the list
let second = slow.next;
slow.next = null;
// Reverse the second half of the list
let prevNode = null;
while (second !== null) {
let nextNode = second.next;
second.next = prevNode;
prevNode = second;
second = nextNode;
}
let left = head;
let right = prevNode;
while (right !== null) {
let nextLeft = left.next;
let nextRight = right.next;
// Rearrange pointers alternatively
left.next = right;
right.next = nextLeft;
// Update pointers
left = nextLeft;
right = nextRight;
}
};
Time and space complexity
The time complexity is again in this version, as we need to "touch" each node. However, space complexity is constant, that is, as we don't need extra amount of space that will grow with the input size, which is better.
If you feel a bit dizzy after rearranging all those pointers, now it's time to take a breath. The next problem will be Remove Nth Node From End of List. Until then, happy coding.