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.
1public class ListNode {
2 int val;
3 ListNode next;
4 ListNode(int x) { val = x; }
5}
6
7class Solution {
8 public void reorderList(ListNode head) {
9 if (head == null || head.next == null) return;
10 List<ListNode> nodes = new ArrayList<ListNode>();
11 ListNode node = head;
12 while (node != null) {
13 nodes.add(node);
14 node = node.next;
15 }
16 int left = 0;
17 int right = nodes.size() - 1;
18 while (left < right) {
19 nodes.get(left).next = nodes.get(right);
20 left++;
21 if (left == right) break;
22 nodes.get(right).next = nodes.get(left);
23 right--;
24 }
25 nodes.get(left).next = null;
26 }
27}The Java solution stores nodes in a list, then rearranges them using a two-pointer technique to alternately select from the front and back of the list.