算法

分段+翻转+合并。

参考文献

y总

C++ 代码

/**
 * 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) {
        //特判只有一个结点,直接结束（不可能为空，因为数据范围大于1）
        if(!head -> next) return ;
        //n：求的链表结点数
        int n = 0 ;
        for(auto p = head ; p ; p = p -> next) n++;
        //left：前半段的结点数
        int left = (n + 1) / 2;
        //leftA：前半段的右边界，即前半段最后一个结点
        auto leftA = head;
        for(int i = 0 ; i < left - 1 ; i++) leftA = leftA -> next;

        //rightB:后半段的左边界，即后半段的第一个结点；rightC:rightB后面一个结点
        auto rightB = leftA -> next , rightC = rightB -> next;
//leftA后面指向空，rightB的下一个也指向空，因为翻转之后rightB就是后半段最后一个结点
        leftA -> next = rightB -> next = NULL;

        //翻转后半段
        while(rightC){ // 当rightC没有走到空时就继续
            auto p = rightC -> next;
            //rightC下一个结点指向rightB，翻转
            rightC -> next = rightB ;
            //两个指针rightB、rightC向后移动一个
            rightB = rightC;
            rightC = p;
        }//循环结束之后，后半段的头结点就是rightB。rightC指向了空

        //合并两个链表,p指向前半段第一个，q指向后半段第一个，后半段元素少，所以判断q不空
        for(auto p = head , q = rightB ; q ; ){
            //保存q的下一个结点，方便下面改指针指向的时候不丢失
            auto o = q -> next;
            q -> next = p -> next;
            p -> next = q;
            p = p -> next -> next;
            q = o;
        }
        //合并完成

    }
};