题解 | #翻转链表#

本题你当然可以使用数组遍历的方式来构造输出，不过就题目要求而言，以下思路可供参考：

• 使用字符串构建链表：可以通过截取逗号的方式来提取链表元素。为方便起见，我们可以在字符串结尾再加上一个逗号
• 将链表按照长度拆分为两个子链表，应从len/2处操作
• 翻转后半链表，具体操作可参考**
• 按照顺序构建输出，注意逗号的处理 实现代码如下：

#include <bits/stdc++.h>
using namespace std;

//定义链表结构体
struct ListNode {
    string val;
    ListNode* next;
    ListNode() : val(""), next(nullptr) {}
    ListNode(string s) : val(std::move(s)) , next(nullptr){}
};

//反转函数
ListNode* reverseList(ListNode* head) {
    ListNode* pre = nullptr;
    ListNode* cur = head;
    ListNode* tem;
    while (cur != nullptr) {
        tem = cur->next;
        cur->next = pre;
        pre = cur;
        cur = tem;
    }
    return pre;
}

int main() {
    string strin;
    cin >> strin;
    if(strin.empty()){
        cout << "" << endl;
        return 0;
    }

    //处理输入
    strin = strin + ",";
    auto* dummy = new ListNode();
    auto* cur = dummy;
    int start = 0, len = 0;
    //构建链表
    for (int i = 0; i < strin.size(); i++) {
        if (strin[i] == ',') {
            if(i > start){
                string num = strin.substr(start, i - start);
                auto* node = new ListNode(num);
                cur->next = node;
                cur = cur->next;
                len++;
            }
            start = i + 1;
        }
    }
    if(!len){
        cout << "" << endl;
        delete dummy;
        return 0;
    }
    //拆分子链表
    int mid = (len % 2) ? len / 2 + 1 : len / 2;
    cur = dummy->next;
    ListNode* prev = nullptr;
    for(int i = 0; i < mid; i++){
        prev = cur;
        cur = cur->next; 
    }
    if(prev) prev->next = nullptr;
    ListNode* list1 = dummy->next;
    ListNode* list2 = cur;
    list2 = reverseList(list2); //反转后半链表

    //构建输出
    ListNode* n1 = list1;
    ListNode* n2 = list2;
    bool first = true;
    while(n1 && n2){
        if(!first) cout << ",";
        cout << n1->val << "," << n2->val;
        n1 = n1->next;
        n2 = n2->next;
        first = false;
    }
    while(n1){
        if(!first)  cout << ",";
        cout << n1->val;
        n1 = n1->next;
        first = false;
    }
    while(n2){
        if(!first)  cout << ",";
        cout << n2->val;
        n2 = n2->next;
        first = false;
    }

    delete dummy;
    return 0;
}