题解 | #链表的奇偶重排#

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
#include <stack>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode* oddEvenList(ListNode* head) {
    stack<ListNode *> oddStack,evenStack;  //奇数栈和偶数栈
    ListNode *p,*ans;   //工作指针
    ans=p=head;
    bool flag=true;    //为真表示奇数为节点，为false表示偶数为节点
    while(p)
    {
        if(flag)   //为奇数
            oddStack.push(p);
        else         //为偶数
            evenStack.push(p);
        p=p->next;      //p指针后移
        flag=!flag;     //表示下一位节点位数的奇偶项
    }
    ans=nullptr;
    while(!evenStack.empty()){  //弹出栈顶元素
        p=evenStack.top();
        p->next=ans;
        ans=p;
        evenStack.pop();
    }
    while(!oddStack.empty()){//弹出栈顶元素
        p=oddStack.top();
        p->next=ans;
        ans=p;
        oddStack.pop();
    }
    return ans;
    }
};