一、链表与重排链表简介
链表是一种常见的数据结构，由一系列节点组成，每个节点包含一个指针指向下一个节点。链表有单向链表、双向链表、循环链表等多种类型，用于实现队列、栈、图等数据结构。重排链表是指给定一个链表，将其重排为先添加的节点排在前面，后添加的节点排在后面，而且要求原链表顺序不变。
二、重排链表思路与算法
重排链表可以分为以下几个步骤：
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)。重排链表常用于解决链表相关的问题，在某些场合下还能快速实现交错顺序的效果。
原创文章，作者：NPYAC，如若转载，请注明出处：https://www.506064.com/n/360850.html
微信扫一扫 
支付宝扫一扫 