内容简介:给定一个单链表,将链表按头节点、尾节点、第二个节点、 倒数第二个节点…的规律重建。要求:原地操作,不改变节点的值。暴力法:先找头节点,再找尾节点,然后顺次第二个节点,倒数第二个节点,由于是单链表,不停的从表头遍历到表尾,时间复杂度O(n^2)
给定一个单链表,将链表按头节点、尾节点、第二个节点、 倒数第二个节点…的规律重建。要求:原地操作,不改变节点的值。
思路
暴力法:先找头节点,再找尾节点,然后顺次第二个节点,倒数第二个节点,由于是单链表,不停的从表头遍历到表尾,时间复杂度O(n^2)
看下有没有其他便捷方法。
假设给一组数字 1,2,3,4,5,6 ,重新排序后是 1,6,2,5,3,4 ,会发现一个规律, 1, 2, 3 是顺序的, 6, 5, 4 是倒序插入的。
所以可这样考虑:
先把链表一分为二,把后半部分数据倒序插入前半部分。
头插法制作倒序链表,时间复杂度 O(n),将左右两链表合并,时间复杂度 O(n)。总时间复杂度为O(n)。
伪代码
void Revert (Link L1) {
new Link L2; //用于存放倒序的后半部链表
int half_len = L1.lenght() / 2; //记录链表的一半
int*p = L1->head; //p 指向 L1 头节点
int*q = L2->head; //q 指向 L2 头指针
int *s, *t;
for (int i = 0; i < half_len; i++) {
s= s->next; // 找到链表中部
}
q= s->next; //把后半段链表赋值给 L2
s->next = null; // 此时 s 为 L1尾指针
t= q->next;
// 这里我直接在表内操作,看起来有点乱,新建个 L3来存放会看得舒服点
while( t->next != null ) { //倒置 L2
q->next= t->next;
t->next = q;
L2->head->next = t;
t= q->next;
q= L2->head->next;
}
while ( p != s ) { // p 没有走到表尾时插入L2节点
t= L2->head->next; //一开始,t 指向 L2第一个节点
L2->head->next= L2->head->next->next; //取出第一个节点,第二个节点变成第一个节点
t->next= p->next; //t 插入 p
p->next= t->next;
p= p->next->next; //移动 p 到下一个待插入的节点
}
}
简单的图示:
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:- 算法之常见排序算法-冒泡排序、归并排序、快速排序
- 排序算法之冒泡排序改进算法
- 快速排序算法,C语言快速排序算法深入剖析
- 排序算法下——桶排序、计数排序和基数排序
- 数据结构和算法面试题系列—排序算法之快速排序
- 数据结构和算法面试题系列—排序算法之基础排序
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
数学与泛型编程
[美]亚历山大 A. 斯捷潘诺夫(Alexander A. Stepanov)、[美]丹尼尔 E. 罗斯(Daniel E. Rose) / 爱飞翔 / 机械工业出版社 / 2017-8 / 79
这是一本内容丰富而又通俗易懂的书籍,由优秀的软件设计师 Alexander A. Stepanov 与其同事 Daniel E. Rose 所撰写。作者在书中解释泛型编程的原则及其所依据的抽象数学概念,以帮助你写出简洁而强大的代码。 只要你对编程相当熟悉,并且擅长逻辑思考,那么就可以顺利阅读本书。Stepanov 与 Rose 会清晰地讲解相关的抽象代数及数论知识。他们首先解释数学家想要解决......一起来看看 《数学与泛型编程》 这本书的介绍吧!