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.
1#include <stdio.h>
2#include <stdlib.h>
3
4struct ListNode {
5 int val;
6 struct ListNode* next;
7};
8
9struct ListNode* reverseList(struct ListNode* head) {
10 struct ListNode* prev = NULL;
11 struct ListNode* current = head;
12 while (current) {
13 struct ListNode* next = current->next;
14 current->next = prev;
15 prev = current;
16 current = next;
17 }
18 return prev;
19}
20
21void reorderList(struct ListNode* head) {
22 if (!head || !head->next) return;
23 struct ListNode* slow = head;
24 struct ListNode* fast = head;
25 while (fast && fast->next) {
26 slow = slow->next;
27 fast = fast->next->next;
28 }
29 struct ListNode* second = reverseList(slow->next);
30 slow->next = NULL;
31 struct ListNode* first = head;
32 while (second) {
33 struct ListNode* tmp1 = first->next;
34 struct ListNode* tmp2 = second->next;
35 first->next = second;
36 second->next = tmp1;
37 first = tmp1;
38 second = tmp2;
39 }
40}The C solution first finds the midpoint using two pointers, splits the list, reverses the second half, and then merges the first half with the reversed second half node by node.
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.