重排链表详解

一、链表与重排链表简介

链表是一种常见的数据结构，由一系列节点组成，每个节点包含一个指针指向下一个节点。链表有单向链表、双向链表、循环链表等多种类型，用于实现队列、栈、图等数据结构。重排链表是指给定一个链表，将其重排为先添加的节点排在前面，后添加的节点排在后面，而且要求原链表顺序不变。

二、重排链表思路与算法

重排链表可以分为以下几个步骤：

1. 使用快慢指针法，找到链表的中点，并将链表断为两段。

2. 将后半段翻转，得到新的链表。

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) {
        if (head == nullptr || head->next == nullptr || head->next->next == nullptr) {
            return;
        }
        // 找到链表的中点
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast->next != nullptr && fast->next->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
        }
        // 将链表断为两段
        ListNode* l1 = head;
        ListNode* l2 = slow->next;
        slow->next = nullptr;
        // 翻转后半段链表
        ListNode* pre = nullptr;
        ListNode* cur = l2;
        while (cur != nullptr) {
            ListNode* tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }
        l2 = pre;
        // 合并两个链表
        while (l2 != nullptr) {
            ListNode* tmp1 = l1->next;
            ListNode* tmp2 = l2->next;
            l1->next = l2;
            l1 = tmp1;
            l2->next = l1;
            l2 = tmp2;
        }
    }
}; 

三、算法的时间复杂度和空间复杂度

由于需要求解中点、翻转链表和合并链表，因此算法的时间复杂度是O(N)，其中N是链表的长度。由于只使用了固定数量的额外空间，因此算法的空间复杂度是O(1)。

四、重排链表的应用场景

重排链表可以用于解决链表相关的问题，例如链表的归并排序、链表的交叉点等。此外，重排链表还可以用于实现一些要求交错顺序的场合，例如打印时需要将两个队列依次交错输出。

五、总结

重排链表是一种在链表上进行部分翻转、合并操作的算法。其核心思想是将链表分成两部分，对后半段进行翻转，然后按照交错的顺序拼接前后两段链表得到重排链表。该算法的时间复杂度为O(N)，空间复杂度为O(1)。重排链表常用于解决链表相关的问题，在某些场合下还能快速实现交错顺序的效果。