算法学习:重新排序链表

栏目: 数据库 · 发布时间: 6年前

内容简介:给定一个单链表,将链表按头节点、尾节点、第二个节点、 倒数第二个节点…的规律重建。要求:原地操作,不改变节点的值。暴力法:先找头节点,再找尾节点,然后顺次第二个节点,倒数第二个节点,由于是单链表,不停的从表头遍历到表尾,时间复杂度O(n^2)

算法学习:重新 <a href='https://www.codercto.com/topics/21904.html'>排序</a> 链表

给定一个单链表,将链表按头节点、尾节点、第二个节点、 倒数第二个节点…的规律重建。要求:原地操作,不改变节点的值。

思路

暴力法:先找头节点,再找尾节点,然后顺次第二个节点,倒数第二个节点,由于是单链表,不停的从表头遍历到表尾,时间复杂度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 到下一个待插入的节点
	}

}

简单的图示:

算法学习:重新排序链表


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

网络多人游戏架构与编程

网络多人游戏架构与编程

格雷泽 (Joshua Glazer)、马达夫 (Sanjay Madhav) / 王晓慧、张国鑫 / 人民邮电出版社 / 2017-10-1 / CNY 109.00

本书是一本深入探讨关于网络多人游戏编程的图书。 全书分为13章,从网络游戏的基本概念、互联网、伯克利套接字、对象序列化、对象复制、网络拓扑和游戏案例、延迟、抖动和可靠性、改进的延迟处理、可扩展性、安全性、真实世界的引擎、玩家服务、云托管专用服务器等方面深入介绍了网络多人游戏开发的知识,既全面又详尽地剖析了众多核心概念。 本书的多数示例基于C++编写,适合对C++有一定了解的读者阅读。本......一起来看看 《网络多人游戏架构与编程》 这本书的介绍吧!

URL 编码/解码
URL 编码/解码

URL 编码/解码

Markdown 在线编辑器
Markdown 在线编辑器

Markdown 在线编辑器

HEX HSV 转换工具
HEX HSV 转换工具

HEX HSV 互换工具