如何用C++实现单链表前后半拆分且后半部分逆序存储？

核心逻辑拆解为4个步骤：

• 计算链表总长度：遍历一次链表得到结点总数n，偶数长度下前后半段各占n/2个结点；奇数长度下前半段占n/2 + 1个结点，后半段占剩余结点
• 拆分链表：遍历到前半段的最后一个结点，将其next指针置空，得到两个独立的前半段、后半段链表
• 反转后半段：用双指针迭代法原地反转后半段链表，时间复杂度O(n)，空间复杂度O(1)
• 按要求先后输出前半段、反转后的后半段元素

#include <iostream>
using namespace std;

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

// 计算链表总长度
int getLength(ListNode* head) {
    int len = 0;
    while (head) {
        len++;
        head = head->next;
    }
    return len;
}

// 原地反转链表
ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* curr = head;
    while (curr) {
        ListNode* nextTemp = curr->next;
        curr->next = prev;
        prev = curr;
        curr = nextTemp;
    }
    return prev;
}

// 按格式输出链表元素
void printList(ListNode* head) {
    while (head) {
        cout << head->val;
        if (head->next) cout << " ";
        head = head->next;
    }
    cout << endl;
}

int main() {
    // 从输入构建单链表
    ListNode* dummy = new ListNode(0);
    ListNode* curr = dummy;
    int num;
    while (cin >> num) {
        curr->next = new ListNode(num);
        curr = curr->next;
    }
    ListNode* head = dummy->next;
    delete dummy;

    int len = getLength(head);
    int half = len / 2;
    // 奇数长度时前半段多占一个结点
    if (len % 2 != 0) half += 1;

    // 定位前半段最后一个结点，断开前后段
    curr = head;
    for (int i = 1; i < half; i++) {
        curr = curr->next;
    }
    ListNode* secondHead = curr->next;
    curr->next = nullptr;

    // 反转后半段链表
    secondHead = reverseList(secondHead);

    // 输出结果
    printList(head);
    printList(secondHead);

    // 此处可补充链表内存释放逻辑
    return 0;
}

输入样例：1 3 4 6 2 3 8 9
输出样例：
1 3 4 6
9 8 3 2

内容的提问来源于stack exchange，提问作者Sameer Kumar