目录
链表的逆序和截断
逆序
截断
查找链表的中间节点
力扣题
博主主页：东洛的克莱斯韦克-CSDN博客
链表的逆序和截断
逆序
推荐使用头插法逆序，首先要 new 一个虚拟头节点——newNode。如下图
链表的头节点为head，由cur指针指向head，逆序算法如下：
1. next = cur->next;
2.cur->next = newNode->next;
3.newNode->next = cur;
4.cur = next;
为了防止cur找不到下一个节点，要提前用next保存起来，cur遍历到的节点都会放到newNode的后面，当cur遍历完整个链表后，newNode后面就是逆序后的链表。
该算法的结束条件是：
cur == nullptr;
时间复杂度为 ， 空间复杂度为
。
截断
在上述算法的基础上我们给newNode一个指针newNode_cur ，如下图
把head链表上的节点插入到newNode_cur后newNode_cur指针向后移动一格。
1.next = cur->next;
2.cur->next = newNode_cur->next;
3.newNode_cur->next = cur;
4.cur = next;
5.newNode_cur = newNode_cur->next;
为了防止cur找不到下一个节点，依旧让next记录cur的下一个节点的位置。这次newNode后面是顺序的链表。
结束条件取决于要截断多少节点，如果结束条件是
cur == nullptr
那么上述截断算法等价于下述代码
newNode->next = head;
相当于把head链表连入newNode链表的后面。
查找链表的中间节点
用快慢双指针算法。慢指针 slow 每次移动一个节点，快指针 fast 每次移动两个节点，slow 和 fast 都初始化（指向）为链表的头节点， 算法如下
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
结果如下图示意
1. 当 fast 为空时，链表为偶数，slow指针会落在中间靠右的节点上
2. 当 fast->next 为空时，链表为基数，slow指针会落在中间的节点上
力扣题
LCR 026. 重排链表 - 力扣（LeetCode）
这道题比较综合，大题思路就是先找中间节点，再把后半部分链表逆序，然后把逆序后的链表重排到前半部分的链表中。
class Solution {
public:void reorderList(ListNode* head) {//边界情况if (head == nullptr || head->next == nullptr || head->next->next == nullptr) return;//找中间节点ListNode* left = head, *right = head;while (right && right->next) {left = left->next;right = right->next->next;}//把 left 后面的节点逆序ListNode* head1 = new ListNode();ListNode* cur = left->next; left->next = nullptr;while (cur) {ListNode* next = cur->next;cur->next = head1->next;head1->next = cur;cur = next;}//链表重排ListNode* ret = new ListNode();cur = ret;ListNode* head2 = head1->next;while (head) {ListNode* next = head->next;head->next = cur->next;cur->next = head;head = next;cur = cur->next;if (head2) {ListNode* next1 = head2->next;head2->next = cur->next;cur->next = head2;head2 = next1;cur = cur->next;}}//更新结果，释放虚拟节点head = ret->next;delete ret;delete head1;}
};LCR 078. 合并 K 个升序链表 - 力扣（LeetCode）
如果用暴力解法的话时间复杂度会非常高，可以考虑用优先级队列做优化
class Solution {class cmp {public:bool operator()(const ListNode* l1, const ListNode* l2) { return l1->val > l2->val; }};public:ListNode* mergeKLists(vector<ListNode*>& lists) {//小跟堆priority_queue<ListNode*, vector<ListNode*>, cmp> heap;ListNode* ret = new ListNode();ListNode* cur = ret;//把链表的头结点放入优先级队列for(auto l : lists) { if (l) heap.push(l); }while (!(heap.empty())) {ListNode* t = heap.top();ListNode* next = t->next; //记录链表的下一个节点t->next = cur->next; //插入到ret的后面cur->next = t; //插入到ret的后面cur = cur->next;heap.pop();if(next) heap.push(next);}cur = ret->next;delete ret;return cur;}
};其他一些链表题
25. K 个一组翻转链表 - 力扣（LeetCode）
160. 相交链表 - 力扣（LeetCode）
141. 环形链表 - 力扣（LeetCode）
138. 随机链表的复制 - 力扣（LeetCode）
138这道题很考验对链表的把控
LCR 077. 排序链表 - 力扣（LeetCode）
