25
- 要求时间复杂度O(1)，所以很多取巧暴力的方法就不能用了
- 我们需要把链表均分为两份，然后重新排列，所以需要先找到中间结点
- 链表找中间节点有一种固定使用的方法，就是快慢指针
- 设置两个指针p和q，p每次走一步，q每次走两步
- 当指针q到达链表尾时，p就正好在链表中间（可以自己画一个图，非常好理解）
- 从中间结点断开，分成两个链表
- 然后将后一个链表也就是原链表的后半段进行原地逆置
- 最后分别插入即可
- 时间复杂度O(n)，空间复杂度O(1)
void rearrange(NODE *head) { NODE *p = head, *q = head, *tmp, *s; // 1.快慢指针，找到中间结点 while(q->next != NULL) { p = p->next; q = q->next; if(q->next != NULL) q = q->next; } // 2.断链，分成两个链表 q = p->next; p->next = NULL; // 3.后一个链表原地逆置，链回去 while (q != NULL) { tmp = q->next; q->next = p->next; p->next = q; q = tmp; } // 4.拼接两个链表 s = head->next; q = p->next; p->next = NULL; while (q != NULL) { tmp = q->next; q->next = s->next; s->next = q; s = q->next; q = tmp; } } 复制代码
- 思路就是要插入逆置的后半部分的链表，而逆置后半部分就需要先找到中间结点，找中间结点就要用到快慢指针
链表已经更新完毕，5月继续更新栈和队列👨💻
更新日志
- 2022年4月7日 开始
- 4月12日 顺序表更新完成
- 4月25日 更新整个目录结构为中文，之后的提交信息也换成中文
- 4月28日 链表更新完成
- ...
