题目一 力扣143.重排链表

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reorder-list/

1.描述

给定一个单链表L的头节点head，单链表 L 表示为：
L0 → L1 → … → Ln - 1 → Ln
请将其重新排列后变为：
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

2.示例

• 示例 1：
  

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

• 示例2
  

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

解法一 线性化

解题思路

题目的要求是将从尾节点开始的后半部分，重新填充到从头节点开始的前半部分，倒数第一个节点变更为正数第一个节点的后继结点，倒数第二个节点变更为正数第二个节点的尾结点，倒数第三个节点变更为正数第三个节点的尾结点。。。依此类推。单链表的缺点是无法随机访问，只能顺序访问，于是我们可以考虑将单链表变更为可随机访问的线性表，然后再对节点进行操作即可。

代码

/**
 * 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) {
        vector<ListNode*> node;//存储链表节点的线性表
        ListNode* temp = head;//访问指针
        while(temp){//将单链表节点存储到线性表中
            node.push_back(temp);
            temp = temp->next;
        }
        int m = node.size();//计算节点数
        for(int i = 0; i < m/2; ++i){
        //从i=0开始，将正数第i个节点的后继结点更新为倒数第i个节点，
        //并将倒数第i+1个节点的后继节点置为空
            node[m-i-2]->next=nullptr;
            node[m-i-1]->next=node[i]->next;
            node[i]->next=node[m-i-1];
        }
    }
};

复杂度分析

时间复杂度： O(m)。m为单链表节点数，遍历整个单链表和修改next指针指向都需要O(m)时间。
空间复杂度： O(m)。辅助线性表的空间消耗。

解法二 双指针+翻转链表+链表合并

解题思路

解法一的时间复杂度已为最优，但是空间复杂度仍然可以优化。如果我们使用双指针技术找到单链表后半段的头结点，然后继续使用双指针技术原地翻转单链表的后半段，最后继续使用双指针技术将链表前半段与翻转后的单链表后半段原地合并，即可将空间复杂度优化至常数级。

代码

/**
 * 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) {
        ListNode* headRight = findRight(head);
        if(!headRight) return;
        headRight = reverseList(headRight);
        mergeList(head,headRight);
    }

    ListNode* findRight(ListNode* head){//寻找链表后半段的开始节点
        ListNode* verySlow = head;//用于标记前半段链表尾结点的指针
        ListNode* slow = head;//慢指针，用于标记后半段链表头结点
        ListNode* fast = head;//快指针
        int count = 0;//计数器
        while(fast){
            fast = fast->next;//移动快指针
            ++count;//计数器加一
            if(count%2==0){//每移动两次快指针就移动一次慢指针
                slow =slow->next;
                if(verySlow->next != slow){//除了第一次移动慢指针以外，慢指针和更慢指针都一起移动
                    verySlow = verySlow->next;
                }
            }
        }
        if(count<=2) return nullptr;//如果链表长度低于3，返回空指针，后续不作处理，直接结束程序
        if(count%2!=0){//如果链表节点数为奇数，慢指针和更慢指针都后移一位
            slow = slow->next;
            verySlow = verySlow->next;
        }
        verySlow->next = nullptr;//将更慢指针指向节点的后继结点置为空，否则处理完毕后链表会有环
        return slow;
    }

    ListNode* reverseList(ListNode* head){//翻转链表
        ListNode* pre = nullptr;//前驱节点
        ListNode* cur = head;//当前节点
        while(cur){
            ListNode* nextPtr = cur->next;//后继节点
            cur->next = pre;//翻转
            pre = cur;//更新前驱节点和当前节点
            cur = nextPtr;
        }
        return pre;//返回翻转后的链表
    }

    ListNode* mergeList(ListNode* left, ListNode* right){//合并两个链表
        ListNode* node = left;//用于标记前半段链表节点
        while(right){
            ListNode*  temp = right->next;//后半段链表当前节点的后继节点
            right->next = node->next;//将后半段链表当前节点置为前半段链表当前节点的后继节点
            node->next = right;
            node = right->next;//移动指针
            right = temp;
        }
        return left;//返回合并后的单链表
    }
};

复杂度分析

时间复杂度： O(m)。寻找后半段节点的头结点，翻转后半段链表，合并前后段链表均为O(m)时间。
空间复杂度： O(1)。只需常数个额外变量。