牛客经典链表题—(NC2)重排链表

合并有序链表

• 1. 题目描述
• 2. 题目链接
• 3. 题目剖析
• • 3.1剖析图示
  • 3.2 图示详解
• 4. 解题代码
• 5. 代码注释详解

满难度系数

* * * * *

，此题难度系数

* * *

。

满考频热度

* * * * *

，此题热度

* * * * *

。

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.会持续更新相关链表高频题目，分类专栏—数据结构

。