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.
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 slow, fast = head, head.next
12 while fast and fast.next:
13 slow = slow.next
14 fast = fast.next.next
15
16 second = slow.next
17 prev = slow.next = None
18 while second:
19 nxt = second.next
20 second.next = prev
21 prev = second
22 second = nxt
23
24 first, second = head, prev
25 while second:
26 tmp1, tmp2 = first.next, second.next
27 first.next = second
28 second.next = tmp1
29 first, second = tmp1, tmp2The Python solution employs a clean and concise approach to rearrange the list according to the specified pattern.
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.