解题思路

题意是将原来的链表首部放一个,尾部放一个的顺序依次组织成一个新链表.可以先将原列表的节点依次放入双端队列中,然后再按对首和队尾出队的顺序出队组织成新的链表, 可得结果.

代码实现

#include <iostream>
#include <stack>
#include <deque>
#include <sstream>
using namespace std;

constexpr int BUFFER_SIZE = 1024*1024;

struct ListNode{
    ListNode(int val) : val(val), next(nullptr){}
    int val;
    ListNode * next;
};

void freeList(ListNode* head){
    stack<ListNode*> S;
    auto it = head;
    while (it != nullptr) {
        S.push(it);
        it = it->next; 
    }
    while (!S.empty()) {
        S.top()->next = nullptr;
        delete S.top();
        S.pop();
    }
    head = nullptr;
}

ListNode* inputList(){
    int num;
    char comma;
    char line[BUFFER_SIZE];
    cin.getline(line, BUFFER_SIZE);
    stringstream sstr(line);
    sstr >> num;
    sstr >> comma;
    ListNode* head = new ListNode(num);
    auto it = head;
    while(!sstr.eof()){
        sstr >> num;
        sstr >> comma;
        it->next = new ListNode(num);
        it = it->next;
    }
    return head;
}

void printList(ListNode* head){
    ListNode* it = head;
    while (it != nullptr) {
        cout << it->val;
        if(it->next != nullptr) cout<<',';
        it = it->next;
    }
}

int main() {
    auto head = inputList();
    deque<ListNode *> Q;
    auto it = head;
    while(it != nullptr) {
        Q.push_back(it);
        it = it->next;
        Q.back()->next = nullptr;
    }
    head = Q.front();
    Q.pop_front();
    it = head;
    while(!Q.empty()){
        it->next = Q.back();
        Q.pop_back();
        it = it->next;
        if(Q.empty()) {
            it->next = nullptr;
            break;
        }
        it->next = Q.front();
        Q.pop_front();
        it = it->next;
    }

    printList(head);
    freeList(head);
}
// 64 位输出请用 printf("%lld")