题解 | #重排链表#

计算链表长度，并将链表的节点保存到一个栈中，这样栈顶的节点就是要重新连接的节点

需要重连的次数为（length-1)/2，对节点进行重连

class Solution {
public:
 void reorderList(ListNode *head) {
     stack<ListNode*> stk;
     int length = 0;
     ListNode* curNode = head;
     while(curNode!=nullptr)
     {
         //计算链表的长度
         ++length;
         stk.push(curNode);
         curNode = curNode->next;

     }
     curNode = head;        
     for(int i=0;i<(length-1)/2;++i)
     {
         //需要重连的节点
         ListNode* temp = stk.top();
         //if(temp==nullptr)
             //return;
         temp->next = curNode->next;
         curNode->next = temp;            
         stk.pop();
         //新的链表末尾的元素
         ListNode* tail = stk.top();
         tail->next = nullptr;  
         //更新当前节点
         curNode = curNode->next;
         curNode = curNode->next;  
     }

 }
};