题解 | #重排链表#

/**

• Definition for singly-linked list.

• struct ListNode {

• int val;
  

• ListNode *next;
  

• ListNode(int x) : val(x), next(NULL) {}
  

• }; */ class Solution { public: void reorderList(ListNode *head) { if(!head) return; if(!(head -> next)) return ; if(!(head -> next -> next)) return; auto m_slow = head; auto m_fast = head;

   while(m_slow -> next && m_fast -> next && m_fast -> next -> next)
   {
       m_slow = m_slow -> next;
       m_fast = m_fast -> next -> next;
   }
   
   auto m_after = m_slow -> next;
   m_slow -> next = nullptr;
   ListNode* pre = nullptr;
   auto second_sit = m_after;
   while(m_after)
   {
       auto m_next = m_after -> next;
       
       m_after -> next = pre;
       
       pre = m_after;
       
       m_after = m_next;
   }
   
   auto p1 = head;
   auto p2 = pre;
   
   while(p1 && p2)
   {
       
    
           auto save_p1 = p1 -> next;
           auto save_p2 = p2 -> next;
           p1 -> next = p2;
           p1 = save_p1;
  
           
           p2 -> next = p1;
           p2 = save_p2;
       
   }
  

  } };