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 int val;
3 ListNode next;
4 ListNode(int x) { val = x; }
5}
6
7class Solution {
8 private ListNode reverseList(ListNode head) {
9 ListNode prev = null;
10 while (head != null) {
11 ListNode next = head.next;
12 head.next = prev;
13 prev = head;
14 head = next;
15 }
16 return prev;
17 }
18
19 public void reorderList(ListNode head) {
20 if (head == null || head.next == null) return;
21 ListNode slow = head, fast = head;
22 while (fast != null && fast.next != null) {
23 slow = slow.next;
24 fast = fast.next.next;
25 }
26 ListNode second = reverseList(slow.next);
27 slow.next = null;
28 ListNode first = head;
29 while (second != null) {
30 ListNode tmp1 = first.next;
31 ListNode tmp2 = second.next;
32 first.next = second;
33 second.next = tmp1;
34 first = tmp1;
35 second = tmp2;
36 }
37 }
38}The Java solution is simple and follows the same algorithmic steps, taking advantage of Java's 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.