Reorder List
Given the head of a singly linked list, reorder it such that the nodes are rearranged in the following way: L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2 -> ... . You may not modify the values in the list's nodes, only the nodes themselves can be changed.
Constraints:
- The number of nodes in the list is in the range [1, 5 * 10^4].
- 1 <= Node.val <= 10^5
Examples:
Input: [1,2,3,4]
Output: [1,4,2,3]
Explanation: The nodes are rearranged in the following way: L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2 -> ... . In this case, L0 = 1, Ln = 4, L1 = 2, Ln-1 = 3.
Solutions
Two Pointers
Time: O(n)Space: O(1)
The solution uses two pointers to traverse the linked list and store the nodes in an array. Then it reorders the nodes in the array and updates the next pointers of the nodes.
class Solution {
public: void reorderList(ListNode* head) {
vector<ListNode*> arr;
ListNode* curr = head;
while (curr) {
arr.push_back(curr);
curr = curr->next;
}
for (int i = 0;
i < arr.size() / 2;
i++) {
ListNode* first = arr[i];
ListNode* second = arr[arr.size() - 1 - i];
ListNode* temp1 = first->next;
ListNode* temp2 = second->next;
first->next = second;
second->next = temp1;
}
if (arr.size() % 2 == 1) {
arr[arr.size() / 2]->next = NULL;
}
else {
arr[arr.size() / 2 - 1]->next = NULL;
}
}
}Follow-up:
How would you solve this problem if the linked list is a doubly linked list?
