class Solution {
public:
void reorderList(ListNode* head) {
// cut list 1>2>3>4>5 ==> list1:1>2 list2:3>4>5
ListNode *fast = head, *slow = nullptr;
while (fast != nullptr && fast>next != nullptr) {
fast = fast>next>next;
slow = slow == nullptr ? head : slow>next;
}
if (slow == nullptr) return;
ListNode *head2 = slow>next;
slow>next = nullptr;
// reverse list2 3>4>5 ==> 5>4>3
slow = fast = head2;
head2 = nullptr;
while (fast != nullptr) {
fast = fast>next;
slow>next = head2;
head2 = slow;
slow = fast;
}
// merge two list list1:1>2 list2:5>4>3 ==> 1>5>2>4>3
slow = fast = head;
while (fast != nullptr && head2 != nullptr) {
fast = fast>next;
slow>next = head2;
head2 = head2>next;
slow>next>next = fast ? fast : head2;
slow = fast;
}
}
};
56ms, accepted c++ solution


@Paynepein said in 56ms, accepted c++ solution:
slow = fast = head2; while (fast>next != nullptr) { fast = fast>next; slow>next>next = slow; slow = fast;
Are you sure this is correct? I don't need to try but I can tell this is definitely dead loop.

@ayuanx When the fast pointer points to the last node, the execution is out of the loop.

@Paynepein Man, you should put it into the test if you don't know what I was talking about.
