满难度系数 * * * * *，此题难度系数 * * *。
满考频热度 * * * * *，此题热度 * * * * *。

1. 题目描述

2. 题目链接

1. 牛客题目链接重排链表

3. 题目剖析

1. 重排链表方式是从两头到中间交错重排，假如链表有4个结点，重排方式是1->4->2->3。
2. 主要考察对链表的基本操作，要处处小心，以免越界考的知识点有：快慢指针找中间结点，反转链表，链表链接等知识点。
3. 快慢指针找中间结点和反转链表在之前题解有过详解：反转链表link
4. 具体操作如下图解，详细过程如下。

3.1剖析图示

3.2 图示详解

1. 第一步，先利用快慢指针的思想找到中间结点。并将中间结点作为一个新链表的头进行记录。
2. 第二步，将中间结点到最后的结点进行反转，如上图的第一步。
3. 第三步，将反转之后链表的头节点链接在未反转链表的头节点之后，然后两个链表同时往后走按照第一步的做法以此循环，直到反转之后的链表走到空。

4. 解题代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode *head) {
    	//注释1
        if(head == nullptr || head -> next == nullptr || head->next->next == nullptr)
        {
            return;
        }
        
        //注释2
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast && fast -> next)
        {
            fast = fast -> next  -> next;
            slow = slow -> next;
        }
        //注释3
        ListNode *HNode = slow -> next;
        slow -> next = nullptr;
        ListNode* Node = nullptr;
        ListNode* cur = HNode;
        ListNode* Next = cur -> next;
   
        cur -> next = Node;
        while(Next)
        {
            Node = cur;
            cur = Next;
            Next = cur -> next;
            cur -> next = Node;
        }
        //注释4
        ListNode *CurHead = head;
        ListNode *NewHead = cur;
        ListNode *Next1 = head;
        ListNode *Next2 = NewHead;
        while(Next2)
        {
            Next1 = CurHead -> next;
            Next2 = NewHead -> next;
            CurHead -> next = NewHead;
            NewHead -> next = Next1;
            CurHead = Next1;
            NewHead = Next2;
        }
    }
};

5. 代码注释详解

1. 注释1：如果节点数小于三个则直接返回，排列方式已经满足题目要求。
2. 注释2：快慢指针找中间结点，并将中间节点的前一个结点指向空。
3. 注释3：将中间结点到最后结点进行反转。
4. 注释4：按照图解的方法将前后两个链表进行重排列，当反转之后的链表遍历到空时排列结束。
   合并有序链表算法复杂度为：

• 时间复杂度：O(n)
• 空间复杂度：O(1)

1.如有错误或者没能理解的地方，请及时评论或者私信，及时修改更新。
2.会持续更新相关链表高频题目，分类专栏—数据结构。