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.
1public class ListNode {
2 public int val;
3 public ListNode next;
4 public ListNode(int x) { val = x; }
5}
6
7public class Solution {
8 public void ReorderList(ListNode head) {
9 if (head == null || head.next == null) return;
10 ListNode slow = head, fast = head;
11 while (fast != null && fast.next != null) {
12 slow = slow.next;
13 fast = fast.next.next;
14 }
15 ListNode second = Reverse(slow.next);
16 slow.next = null;
17 ListNode first = head;
18 while (second != null) {
19 ListNode tmp1 = first.next;
20 ListNode tmp2 = second.next;
21 first.next = second;
22 second.next = tmp1;
23 first = tmp1;
24 second = tmp2;
25 }
26 }
27
28 private ListNode Reverse(ListNode head) {
29 ListNode prev = null;
30 while (head != null) {
31 ListNode next = head.next;
32 head.next = prev;
33 prev = head;
34 head = next;
35 }
36 return prev;
37 }
38}The C# solution follows similar steps to the other solutions, maintaining clarity in implementation.
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.