1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| class Solution {
private:
void mergeList(ListNode* smallList, ListNode* largeList) {
if (largeList == nullptr) return;
ListNode *largeNext = largeList->next;
largeList->next = smallList->next;
smallList->next = largeList;
mergeList(largeList->next, largeNext);
}
ListNode* reverseList(ListNode* head) {
ListNode *dummyHead = new ListNode(-1, head);
ListNode *tail = head;
while (tail != nullptr && tail->next != nullptr) {
ListNode *node = tail->next;
tail->next = node->next;
node->next = dummyHead->next;
dummyHead->next = node;
}
return dummyHead->next;
}
ListNode* splitList(ListNode* head) {
ListNode *slow = head, *fast = head;
while (fast->next != nullptr && fast->next->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
}
ListNode *newHead = slow->next;
slow->next = nullptr;
return newHead;
}
public:
void reorderList(ListNode* head) {
mergeList(head, reverseList(splitList(head)));
}
};
|