一、题目描述

NC2重排链表
题目大意：将给定的单链表 a0 -> a1 -> ... -> an-1 -> an，重新排序为a0 -> an -> a1 -> an-1 -> ...
注意审题：要求使用原地算法，即节点内部的值不允许改变，需要对实际的节点进行交换

二、算法1（暴力）

解题思路

  1. 观察排序后的序列我们可以发现，第一个节点后接最后一个节点，第二个节点后接倒数第二个节点，以此类推。故我们可以每次都找到最后一个节点并把它接在当前节点的后面
  2. 我们用一个指针p指向头节点，每次找到链表的最后一个节点并将它接在p所指节点的后面，然后p再指向下一个节点，直到p后面的节点数小于两个时停止

代码实现（C++11）

class Solution {
public:
    void reorderList(ListNode *head) {
        ListNode* p = head;
        while(p){
            if(p->next && p->next->next){    // 若p后面至少有两个节点
                ListNode *pre = p->next, *cur = p->next->next;
                while(cur->next){    // 找到最后一个节点cur, pre指向倒数第二个节点
                    cur = cur->next;
                    pre = pre->next;
                }
                // 将cur接在p后面
                pre->next = nullptr;
                cur->next = p->next;
                p->next = cur;

                p = p->next->next;
            }
            else break;
        }
    }
};

时间复杂度：O(n^2), n为节点数，每次找最后一个的时间复杂度为O(n)，故总时间复杂度为O(n^2)
空间复杂度：O(1)

三、算法2（线性表）

解题思路

  1. 方法一的缺陷在于链表不能通过下标访问元素，故每次找到最后一个节点都很花费时间，因此我们想到可以用线性表来存储节点指针，然后再重新连接链表即可
  2. 实现细节：我们先将每个节点指针放入数组中，然后使用双指针算法每次取出前后对应的两个节点并让前一个节点指向后一个节点，然后用一个指针pre表示上一部分的尾节点指针，若pre不为空，说明前面有一段链表，让pre指向取出的前一个节点即可，再令pre为取出的后一个节点，以此类推，最后记得让pre指向空，当然前提是pre自身不为空

代码实现（C++11）

class Solution {
public:
    void reorderList(ListNode *head) {
        vector<ListNode*> vec;    // 创建线性表
        ListNode* cur = head;
        while(cur){    // 将节点指针放入线性表
            vec.emplace_back(cur);
            cur = cur->next;
        }
        ListNode* pre = nullptr;
        int i = 0, j = vec.size() - 1;
        while(i <= j){    // 使用双指针算法重连链表
            vec[i]->next = vec[j];
            if(pre) pre->next = vec[i];
            pre = vec[j];
            i++, j--;
        }
        if(pre) pre->next = nullptr;    // 尾节点指向空指针
    }
};

时间复杂度：O(n), n为链表节点数，双指针算法的时间复杂度为O(n)
空间复杂度：O(n), 线性表使用的空间

四、算法3（快慢指针、链表翻转、链表合并）

解题思路

  1. 我们可以先通过快慢指针找到链表中点，然后将链表一分为二，再将第二段链表翻转，最后将两段链表交叉合并为一条即可
  2. 这种做法涉及到了快慢指针求链表中点，链表的原地翻转和链表的交叉合并，综合性很强，考察了我们指针使用的熟练度和基本功
  3. 为了方便理解，我用动图来帮助大家弄懂基本的实现原理，关于链表原地翻转的算法，我将在最后用一张动图来演示

图片说明

代码实现（C++11）

class Solution {
public:
    void reorderList(ListNode* head) {
        if(!head) return;
        ListNode* mid = GetMid(head);   // 得到链表的中点
        ListNode *p1 = head, *p2 = mid->next;
        mid->next = nullptr;    // 断开链表
        p2 = ReverseList(p2);   // 翻转后一段链表
        MergeList(p1, p2);   // 交叉合并两条链表
    }

    ListNode* GetMid(ListNode* head) {  // 返回链表中点
        ListNode *slow = head, *fast = head;
        while(fast->next && fast->next->next){
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }

    ListNode* ReverseList(ListNode* head) { // 链表的原地翻转
        if(!head) return head;
        ListNode *pre = head, *cur = head->next;

        while(cur){
            head->next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = head->next;
        }

        return pre;
    }

    void MergeList(ListNode *l1, ListNode *l2) {   // 交叉合并两条链表
        ListNode *tmp1, *tmp2;
        while(l1 && l2){
            tmp1 = l1->next;
            tmp2 = l2->next;

            l1->next = l2;
            l2->next = tmp1;

            l1 = tmp1;
            l2 = tmp2;
        }
    }
};

时间复杂度：O(n)，快慢指针，链表合并，翻转链表的时间复杂度都是O(n)的
空间复杂度：O(1)

链表原地翻转演示

图片说明