Given a singly linked list node, reorder it such that we take: the last node, and then the first node, and then the second last node, and then the second node, etc.
Constraints
0 ≤ n ≤ 100,000 where n is the number of nodes in nodeExample 1
Input
node = [0, 1, 2, 3]
Output
[3, 0, 2, 1]
Two Pointer Algorithm to Convert Linked List Back to Front
We can use an additional array to store the values of the linked list. Then we can use two pointers to assign the values back to the linked list until they meet in the middle.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | /** * class LLNode { * public: * int val; * LLNode *next; * }; */ LLNode* linkedListBackToFront(LLNode* node) { vector<int> data; auto head = node; // copy the values of linked list to a vector while (head) { data.push_back(head->val); head = head->next; } head = node; int n = static_cast<int>(data.size()); int i = 0; int j = n - 1; while (i <= j) { // then while two pointers not meet in the middle // re-assign the values of the linked list head->val = data[j--]; head = head->next; if (i <= j) { // special case when there is only 1 node in the middle (odd) head->val = data[i++]; head = head->next; } } return node; } |
/**
* class LLNode {
* public:
* int val;
* LLNode *next;
* };
*/
LLNode* linkedListBackToFront(LLNode* node) {
vector<int> data;
auto head = node;
// copy the values of linked list to a vector
while (head) {
data.push_back(head->val);
head = head->next;
}
head = node;
int n = static_cast<int>(data.size());
int i = 0;
int j = n - 1;
while (i <= j) {
// then while two pointers not meet in the middle
// re-assign the values of the linked list
head->val = data[j--];
head = head->next;
if (i <= j) { // special case when there is only 1 node in the middle (odd)
head->val = data[i++];
head = head->next;
}
}
return node;
}When there is odd number of the nodes in the linked list, we have to take care of such. The time complexity is O(N) and the space complexity is O(N).
Recursive Algorithm to Convert Linked List Back to Front
We can deal with one problem at a time. We need to find the last node, and second last node. Then reconnect the last node to the first node, break the second last node, and then recursively deal with this problem.
The time complexity is O(N^2) quadratic. The space complexity is O(1) constant.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | /** * class LLNode { * public: * int val; * LLNode *next; * }; */ LLNode* linkedListBackToFront(LLNode* node) { if (node == NULL || node->next == NULL) { return node; } auto curr = node, prev = (LLNode*)NULL; // find the last node while (curr->next) { prev = curr; curr = curr->next; } // re-connect the last node to the first node // break the second last node prev->next = NULL; curr->next = node; node->next = linkedListBackToFront(node->next); return curr; } |
/**
* class LLNode {
* public:
* int val;
* LLNode *next;
* };
*/
LLNode* linkedListBackToFront(LLNode* node) {
if (node == NULL || node->next == NULL) {
return node;
}
auto curr = node, prev = (LLNode*)NULL;
// find the last node
while (curr->next) {
prev = curr;
curr = curr->next;
}
// re-connect the last node to the first node
// break the second last node
prev->next = NULL;
curr->next = node;
node->next = linkedListBackToFront(node->next);
return curr;
}We can also break the linked list in the middle, and reverse the second part, and then merge both.
See also: Linked List Delete Last Occurrence of Value
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Teaching Kids Programming - Python Implementation of Trie Data Structure (Prefix Tree)
Next Post: Teaching Kids Programming - Dynamic Programming Algorithms to Count Numbers with Unique Digits