题目链接: https://www.acwing.com/activity/content/problem/content/4301/

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void rearrangedList(ListNode* head) {
        if(!head->next) return;//当链表中只有一个元素时，直接返回

        auto p = head; int n = 0;
        while(p){//统计链表节点个数
            p = p->next;
            n ++;
        }

        int left = (n + 1) / 2;//前半段元素个数
        auto a = head; left--;//跳left-1次
        while(left--){//a走到前半段的末尾
            a = a->next;
        }

        auto b = a->next, c = b->next;
        a->next = b->next = NULL;//此时a，b分别指向两个链表的尾部，next为空

        //反转后半段链表
        while(c){
            auto t = c->next;
            c->next = b;
            b = c, c = t;
        }

        auto p1 = head, p2 = b;
        while(p2){//合并两个链表
            auto t = p2->next;
            p2->next = p1->next;
            p1->next = p2;
            p1 = p2->next;
            p2 = t;
        }

        return ;
    }
};

小结:
考察链表的合并和反转