[AcWing]3757. 重排链表

一个包含 n 个元素的线性链表 L = (a_1,a_2,…,a_{n-2},a_{n-1},a_n)。

现在要对其中的结点进行重新排序，得到一个新链表 L’ = (a_1,a_n,a_2,a_{n-1},a_3,a_{n-2}…)

样例1：

输入：1->2->3->4

输出：1->4->2->3

样例2：

输入：1->2->3->4->5

输出：1->5->2->4->3

数据范围

1 < n < 1000,
1 < a_i < 10000

算法思想

将链表分成左右两部分，右边那一部分进行逆置，然后将两个链表合并。

前半段是较长的，切断点应该是向上取整，尽可能让前半段长。

选其中一种情况讨论。

step1是合并链表的过程。

s节点是需要提前保存的，用来维护q。

代码实现

/**
 * 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≤n≤1000，只有一个节点，则什么也不做
        if(!head -> next) return;
        
        // 先计算分割点
        
        // 求长度
        int len = 0;
        for(ListNode * p = head; p ; p = p -> next) len++;
        
        // 向上取整
        int left = (len + 1) / 2;
        
        // 找到分割点处的尾节点
        ListNode * a = head;
        // 移动 left - 1 次
        for(int i = 0; i < left - 1; i++) a = a -> next;
        
        // 右边的链表，由于要进行翻转因此有两个指针
        ListNode * b = a -> next, * c = b -> next;
        
        // 先置空
        a -> next = NULL; b -> next = NULL;
        
        // 进行反转
        while(c){
            // 记录排头兵的next，方便维护b
            ListNode * p = c -> next;
            // 反转
            c -> next = b;
            b = c; c = p;
        }// 跳出循环, b就是反转后第一个节点
        
        // 合并链表
        ListNode * p = head, * q = b;
        // 选 q，是因为 q 比较短
        while(q){
            // 提前备份，维护q
            ListNode * s = q -> next;
            // 合并
            q -> next = p -> next;
            p -> next = q;
            // 新的开始
            p = q -> next;
            q = s;
        }
    }
};