题解 | 重排链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* pre = nullptr;
        while (head) {
            ListNode *next = head->next;
            head->next = pre;
            pre = head;
            head = next;
        }

        return pre;
    }

    int getLen(ListNode* head) {
        int cnt = 0;
        while (head) {
            head = head -> next;
            cnt ++;
        }
        return cnt;
    }

    void reorderList(ListNode *head) {
        if (!head || !head->next) return;

        ListNode *dummy = new ListNode(0);
        dummy-> next = head;

        int len = getLen(head);

        // 1. 前面的内容要多一点
        int frontLen = (len + 1) / 2;

        // 2. 链表进行分割
        ListNode *frontRear = dummy;
        while (frontLen --) frontRear = frontRear -> next;

        // 3. 分好两个链表
        ListNode *rearFront = frontRear -> next, *frontFront = dummy -> next;
        frontRear -> next = nullptr;
        rearFront = reverseList(rearFront);

        // 4. 开始合并
        for (int i = 0; i < len / 2; i ++) {
            ListNode *List1_next = frontFront -> next;
            ListNode *List2_next = rearFront -> next;

            frontFront -> next = rearFront;
            rearFront -> next = List1_next;

            frontFront = List1_next, rearFront = List2_next;
        }
    }
};