leetcode 143. Reorder List (medium)

1. 每一次翻转当前节点之后的所有节点，很花时间…
   Runtime: 1760 ms, faster than 5.08% of C++ online submissions for Reorder List.

class Solution
{
    
public:void reorderList(ListNode *head){
    if (head == nullptr || head->next == nullptr)return;for(ListNode *cur = head; cur != nullptr;){
    cur->next = reverse(cur->next);cur = cur->next;}}ListNode *reverse(ListNode *begin){
    if (begin == nullptr || begin->next == nullptr)return begin;ListNode *pre = begin;for (ListNode *cur = pre->next, *next = cur->next; cur != nullptr;){
    cur->next = pre;pre = cur;cur = next;next = next ? next->next : nullptr;}begin->next = nullptr;return pre;}
};

2. 优化时间
   可以找到中间节点，断开，把后半截单链表reverse一下，再合并两个单链表
   Runtime: 48 ms, faster than 99.57% of C++ online submissions for Reorder List.
   参考这篇博文
   

class Solution
{
    
public:void reorderList(ListNode *head){
    if (head == nullptr || head->next == nullptr)return;ListNode *slow = head, *fast = head, *prev = nullptr;while (fast && fast->next){
    prev = slow;slow = slow->next;fast = fast->next->next;}prev->next = nullptr; // cut at middlecout<<prev->val<<" ";slow = reverse(slow);cout<<slow->val<<" ";// merge two listsListNode *curr = head;while (curr->next){
    ListNode *tmp = curr->next;curr->next = slow;slow = slow->next;curr->next->next = tmp;curr = tmp;}curr->next = slow;}ListNode *reverse(ListNode *begin){
    if (begin == nullptr || begin->next == nullptr)return begin;ListNode *pre = begin;for (ListNode *cur = pre->next, *next = cur->next; cur != nullptr;){
    cur->next = pre;pre = cur;cur = next;next = next ? next->next : nullptr;}begin->next = nullptr;return pre;}
};