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.
1class ListNode:
2 def __init__(self, val=0, next=None):
3 self.val = val
4 self.next = next
5
6class Solution:
7 def reorderList(self, head: ListNode) -> None:
8 if not head:
9 return
10
11 nodes = []
12 while head:
13 nodes.append(head)
14 head = head.next
15
16 left, right = 0, len(nodes) - 1
17 while left < right:
18 nodes[left].next = nodes[right]
19 left += 1
20 if left == right:
21 break
22 nodes[right].next = nodes[left]
23 right -= 1
24 nodes[left].next = NoneThe Python implementation uses a list to store nodes, then reorders them by alternately connecting nodes from the front and back.