This approach involves splitting the list into two halves, reversing the second half, and then merging the two lists alternately.
Time Complexity: O(n).
Space Complexity: O(1), as the solution modifies the list in place.
1class ListNode {
2 constructor(val = 0, next = null) {
3 this.val = val;
4 this.next = next;
5 }
6}
7
8function reorderList(head) {
9 if (!head || !head.next) return;
10
11 let slow = head, fast = head;
12 while (fast && fast.next) {
13 slow = slow.next;
14 fast = fast.next.next;
15 }
16
17 let second = reverseList(slow.next);
18 slow.next = null;
19
20 let first = head;
21 while (second) {
22 let tmp1 = first.next;
23 let tmp2 = second.next;
24 first.next = second;
25 second.next = tmp1;
26 first = tmp1;
27 second = tmp2;
28 }
29}
30
31function reverseList(head) {
32 let prev = null;
33 while (head) {
34 let next = head.next;
35 head.next = prev;
36 prev = head;
37 head = next;
38 }
39 return prev;
40}The JavaScript implementation provides a clear approach using function expressions and JavaScript class structures.
This method involves storing the linked list nodes in an array list and then rearranging their connections to achieve the desired order.
Time Complexity: O(n).
Space Complexity: O(n) due to the array storage.
1#include <iostream>
2#include <vector>
3using namespace std;
4
5struct ListNode {
6 int val;
7 ListNode* next;
8 ListNode(int x) : val(x), next(NULL) {}
9};
10
11void reorderList(ListNode* head) {
12 if (!head || !head->next) return;
13 vector<ListNode*> nodes;
14 ListNode* node = head;
15 while (node) {
16 nodes.push_back(node);
17 node = node->next;
18 }
19 int left = 0, right = nodes.size() - 1;
20 while (left < right) {
21 nodes[left]->next = nodes[right];
22 left++;
23 if (left == right) break;
24 nodes[right]->next = nodes[left];
25 right--;
26 }
27 nodes[left]->next = nullptr;
28}The C++ solution uses an array to store nodes and then reorganizes them using two pointers, one from the start and one from the end of the list, alternately linking them.