一、题目

1、题目描述

给定一个单链表 L 的头节点 head ，单链表 L 表示为：

L0 → L1 → … → Ln - 1 → Ln

请将其重新排列后变为：

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1：

输入：head = [1,2,3,4]
输出：[1,4,2,3]

示例 2：

输入：head = [1,2,3,4,5]
输出：[1,5,2,4,3]

2、基础框架

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode* head) {

    }
};

3、原题链接

143. 重排链表

剑指 Offer II 026. 重排链表

二、解题报告

1、思路分析

其实分析重排列后的链表，可以看到后半部分的节点是逆序了。于是：

（1）先找到链表中点，如果是偶数长度就是上中点；

（2）翻转链表的后半部分；

（3）调整指针的指向

2、时间复杂度

$O(N)$

3、代码详解

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode* head) {
        if (head == nullptr) return ;

        ListNode *slow = head;
        ListNode *fast = head->next;
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
        }
        //找到了中点为slow
        ListNode *next = slow->next;
        slow->next = nullptr;
        ListNode *tmp = nullptr;
        while (next != nullptr) {
            tmp = next->next;
            next->next = slow;
            slow = next;
            next = tmp;
        }
        //此时的slow是后半部分链表翻转后的头结点
        ListNode *lHead = head;
        ListNode *rHead = slow;
        ListNode *lNext = nullptr;
        ListNode *rNext = nullptr;
        //调整指针指向
        while (lHead != nullptr && rHead != nullptr) {
            lNext = lHead->next;
            rNext = rHead->next;
            lHead->next = rHead;
            rHead->next = lNext;
            lHead = lNext;
            rHead = rNext;
        }
    }
};