树莓派局域网登录功能实现:Express+jQuery+MongoDB

序言

为了在树莓派上架设教学系统,这里以Express为框架,MongoDB作为数据库,利用了部分jQuery语法,实现了局域网内的注册、登录和找回密码服务。

前期设计

流程设计

因为是局域网登录,没有使用邮箱验证等联网方式注册账户,而是通过班级的注册码进行验证;同时找回密码的方式是由管理员或教师申请账号安全码。

页面设计

设计上使用的简洁的浮窗式界面,实现上使用了一个html文件,以及两个css文件,分别管理页面的表单样式、其他页面布局样式。二者分离开来,有助于表单样式的复用,将来在其他页面上使用到表单,可以调用同一个css文件。

数据库存储格式

  • MongoDB作为非关系型数据库(NoSQL)的一种,相比于关系型数据库,其格式更加灵活,对简单CRUD操作效率更高。
  • 同时MongoDB基于文档,以优化的二进制json(bson)格式存储数据,支持了更多数据类型,提高了运行效率,更有分片集群等功能,适合高并发海量数据的存储。
  • 在这个例子中,需要进行的操作比较简单,没有事务的需求,因此使用MongoDB作为数据库

学生、教师和管理员的信息分别存在三个集合中,共有的信息基本如下:

学(工)号用户名密码权限等级账号安全码
(字符串)(字符串)(字符串)(整型)(字符串数组)

注册码存在以下集合中:

班级权限注册码
(字符串)(整型)(字符串)

以及存储班级信息的集合

前端脚本

页面切换

脚本第一部分用来在不同的页面之间切换,使用原生的操作方式,利用document.getElementById().style等方法脚本化css,实现对元素的隐藏和展示,达到切换页面的效果

function show_form(value) {
//...
//展示登录框...
}
function to_login() {
	document.getElementById('login-form-box').style.display = 'inline';
    document.getElementById('register-form-box').style.display = 'none';
    document.getElementById('forget-form-box').style.display = 'none';
    document.getElementById('find-form-box').style.display = 'none';
//切换到登录界面
}
function to_register() {
//...
//切换到注册界面
}
function to_forget() {
//...
//切换到找回密码界面
}
function to_find() {
//...
//切换到找回密码成功界面
}

jQ请求和响应

脚本第二部分用来向服务器端发送请求,实现注册、登录、找回密码的功能。这部分使用了jQ语法,利用$.post()函数,大大简化了请求操作

$(document).ready(function() {

    //注册功能
    $("#register-button").click(function() {
    	//...
    	//向后端发送POST请求
    	//发送用户名、密码、注册码和身份(教师、学生)
    	//接受是否注册成功的消息
    });

    //登录功能
    $("#login-button").click(function() {
    	//...
        //向后端发送POST请求
    	//发送用户名、密码和身份(教师、学生)
    	//接受是否登录成功的消息
    }); 

    //找回密码功能
    $('#forget-button').click(function() {
    	//...
        //向后端发送POST请求
    	//发送账户安全码和身份(教师、学生)
    	//接受是否验证成功的消息
        //如果验证成功,跳转到重设密码界面
    });

    //找回成功并设置新密码
    $("#find-button").click(function() {
    	//...
        //向后端发送POST请求
    	//发送账户安全码,新密码和身份(教师、学生)
    	//接受是否重设密码成功的消息
        //如果重设密码成功,跳转到登录界面
});

后端处理

连接MongoDB数据库

首先需要mongodb模块

npm install mongodb --save

然后写一个脚本mongodb.js,整合连接数据库的方法,简化调用

const MongoClient = require("mongodb").MongoClient;//引入模块
const dbname = 'piclass';//数据库名
const url = 'mongodb://localhost:27017/' + dbname;//数据库所在的url

//合并插入单个和多个文档的方法,同时提前写好实际不会发生变化的变量,简化数据库的调用
function insertSome(collection, document, callback) { //只传入集合名,文档和回调函数
    if (!Array.isArray(document)) { 
    	//调用连接Mongodb数据库的方法
        MongoClient.connect(url, { useNewUrlParser: true, useUnifiedTopology: true }, function(err, db) {
            if (err) throw err;
            var dbo = db.db(dbname);
            dbo.collection(collection).insertOne(document, function(err, res) {
                if (err) throw err;
                console.log("插入单个文档成功");
                db.close();
                if (callback) callback(res);
            });
        });
     } else {
     	//...
        //insertMany()方法
     }
}

function find(collection, query, callback) {
	//...
    //简化find方法查找元素
}

function find_select(collection, query, skip, limit, callback) {
	//...
    //包含限制个数、跳过个数的find方法
}

function updateSome(collection, query, update, justOne, callback) {
	//...
    //更新一条或者所有符合要求的文档的某个数据
}

function deleteSome(collection, query, justOne, callback) {
	//...
    //删除符合要求的文档
}

function sort(collection, isAscend, callback) {
	//...
    //文档排序
}

module.exports.insertSome = insertSome;
module.exports.find = find;
module.exports.find_select = find_select;
module.exports.updateSome = updateSome;
module.exports.deleteSome = deleteSome;
module.exports.sort = sort;
module.exports.clear = function(collection, callback) { 
    deleteSome(collection, {}, false); 
    if (callback) callback();
} //清空集合

配置路由

发送至express后台的请求由aqq.js分发到各个路由文件中,这里将登录界面的所有请求都由index.js默认路由来响应。

var express = require('express'); //引入express模块
var db = require('../myscripts/mongodb.js'); //引入操作数据库的自定义模块
var router = express.Router(); //调用路由

/* GET home page. */ //根页面直接使用登录静态页面进行响应
router.get('/', function(req, res, next) {
  res.sendfile( __dirname.slice(0, -6) + "public/" + "login.html");
});

/* Login Page */ // /login也同样使用这个静态页面
router.all('/login', function(req, res, next) {
  res.sendfile( __dirname.slice(0, -6) + "public/" + "login.html");
});

/* User Rsgister */ //响应注册请求
router.post('/process_register', function(req, res, next) {
  //...
  //获得用户名、密码、注册码和身份
  //1、根据身份进入不同的数据库集合
  //2、判断用户名是否已存在
  //3、判断注册码是否有效
  //4、存储用户数据
  //5、传回客户端操作是否成功等信息
})

/* User Login */ //响应登录请求
router.post('/process_login', function(req, res, next) {
  //...
  //同样地,查询用户名和密码是否存在,并且反馈信息
})

/* Forget Password */ //响应找回密码请求
router.post('/process_forget', function(req, res, next) {
  //...
  //查询账号安全码是否有效,并且反馈信息
})

/* Find Password */ //响应重设密码请求
router.post('/process_find', function(req, res, next) {
  //...
  //再次验证安全码,同时将新的密码存入数据库中,并且反馈信息
})

结语

利用这些功能,可以简单搭建一个注册、登录和找回密码功能的web应用。要继续完善,还需要在后面的开发中利用cookie或者session storage等本地存储方案,实现登录状态的保持;增加管理页面,实现高权限账户对低权限账户的管理和注册码、账号安全码的分发;以及对代码进行优化等等。

树莓派安装Express

首先更新一下npm

sudo npm install -g npm

然后安装express命令管理工具和express框架

sudo npm install -g express-generator
sudo npm install -g express

接着创建一个express项目

cd Desktop
express PiClass

然后进入项目文件夹,安装依赖

cd PiClass
sudo npm install

最后启动express

set DEBUG=PiClass & npm start

启动成功,在局域网内的设备的浏览器中输入内网IP以及默认的3000端口便可以访问到默认的express页面

如果是使用树莓派本机上的浏览器打开,可以将ip换成localhost

基于树莓派的Node.js便携式教学工具开发·功能要求

基本要求

  1. 基于树莓派Raspbian操作系统搭建一个Wifi热点(hostapd和udhcpd),电脑和手机客户端可以接入该wifi自动获取到IP地址。(例如树莓派作为网关,IP缺省设为10.1.1.1,其他客户端自动获取到10.1.1.0段的其他地址)。
  2. 电脑和手机客户端可访问树莓派(作为服务器)上架设好的Web网站(例如http://10.1.1.1),两类用户登录,一类是教师用户(管理员),另一类是学生用户,两类用户访问不同的缺省页面。
  3. 教师端可上传任一文件到树莓派,上传完成后下发给所有学生端一个下载链接( WebSocket ),实现文件共享。
  4. 教师用户登录后可上传一道题目(比如json格式的单选题),同时下发给所有学生端(WebSocket),并实时查看该题目的回答情况(比如用Echarts展示)
  5. 学生用户登录后可随时接受教师下发的题目并回答,实时反馈答案回到教师端。

扩展要求

  1. 教师端可上传一幅图片,并可实时在网页中图片上进行标注或绘画,同时下发给所有学生端显示(Canvas绘图+WebSocket)。
  2. 教师端可将使用的电脑桌面(或者摄像头)以视频流(ffmpeg)的方式实时传送到树莓派,同时下发给所有学生端同步显示该视频流(jsmpeg)。
  3. 学生端可以在显示图片(或者绘图)上发送弹幕( Canvas绘图+WebSocket ),共享显示给所有教师端和学生端,教师端和学生端都可设置看或不看弹幕。
  4. 树莓派标配摄像头可采集学生头像进行人脸识别签到。

作业报告

  • 项目成果发布在个人博客上。
  • 需要在学期(第十七周)结束前提交完整的大作业报告。

如何配置Geyser使基岩版登录java版MC服务器

俗话说:万物皆发包。服务器与客户端的通信,本质上就是发包。Geyser起到的作用,便是修改包的内容,使其符合基岩版客户端和java版服务端接受的格式,而不是一个真正意义上的双通服务器,因此并不对服务器的稳定性产生大的影响。

Geyser既可以在自己的java版服务器上配置,也可以作为单独的转发服务器代理任何其他java版服务器。MC需要最新发布版本,这里使用的是1.15.2java版服务器及1.14.60基岩版客户端,服务端操作系统是Windows Server 2008

在自己的服务器上配置

1、首先需要java8环境

2、在 https://ci.nukkitx.com/job/GeyserMC/job/Geyser/job/master/ 下载Geyser核心:选择最新的编译通过版本(绿勾)。如果是Bukkit端服务器,或者以Bukkit为基础的Spigot、PaperSpigot端等,下载Geyser-Bukkit.jar;如果是Sponge端,下载Geyser-Sponge.jar。

3、将下载的文件复制到插件文件夹(plugins)中,重新启动一次服务器,等到插件文件夹中生成一个Geyser-Bukkit文件夹(或Geyser-Sponge)后关闭服务器。

4、打开该文件夹中的config.yml进行配置,方法如下:(没有列出的不修改)

  • bedrock:
    • address: 0.0.0.0 //服务器的地址,一般不修改,保持默认0.0.0.0,而登录使用的域名和java服务器的域名是相同的
    • port: 19132 //基岩端需要输入的端口,与java端不相同,需要去防火墙和服务器安全组(如果是云服务器)开放该端口
    • motd1: MC //显示在基岩端“好友”里的motd
    • motd2: Java server via Bedrock //显示在基岩端“服务器”里的motd
  • remote:
    • address: 127.0.0.1 //监听IP,一般不修改,默认是本机
    • port: 25525 //java服务器所在的端口
    • auth-type: offline //按需要设置是否为在线模式,设置为online的话,从基岩版加入该服务器后,会要求输入java版正版账号密码
  • max-players: 100 //从基岩端加入玩家的上限
  • default-locale: zh_cn //注意!这里默认是en_us,需要改为zh_cn,否则开服会一直卡在下载mc核心中

5、保存配置文件,重新开服,再用基岩版就可以通过域名和端口登录了

java服务器后台的输出

Geyser插件先收到连接的请求,然后模拟一个用户连接本机上的服务器,并且注册基岩版皮肤。

转发其他java服务器

1、也需要自己拥有云服务器,或者有公网ip的电脑,同时需要java8环境

2、在 https://ci.nukkitx.com/job/GeyserMC/job/Geyser/job/master/ 下载Geyser核心:选择最新的编译通过版本(绿勾)。然后下载Geyser.jar。

3、将核心单独放在一个文件夹内,在同文件夹创建一个run.bat(windows系统),并且写入如下内容并保存:

@echo off
java -Xms1024M -jar Geyser.jar

4、运行run.bat,直到文件夹内生成一个config.yml后,关闭运行的命令提示符,打开config.yml进行配置,方法如下:

  • bedrock:
    • address: 0.0.0.0 //转发服务器的地址,一般不修改,保持默认0.0.0.0,而登录使用的域名和Geyser服务器的域名是相同的
    • port: 19132 //基岩端需要输入的端口,与java端不相同,需要去防火墙和服务器安全组(如果是云服务器)开放该端口
    • motd1: MC //显示在基岩端“好友”里的motd
    • motd2: Java server via Bedrock //显示在基岩端“服务器”里的motd
  • remote:
    • address: 127.0.0.1 //监听IP,修改为转发的java服务器的IP
    • port: 25525 //java服务器所在的端口
    • auth-type: offline //按需要设置是否为在线模式,设置为online的话,从基岩版加入该服务器后,会要求输入java版正版账号密码
  • max-players: 100 //从基岩端加入玩家的上限
  • default-locale: zh_cn //注意!这里默认是en_us,需要改为zh_cn,否则开服会一直卡在下载mc核心中

5、保存配置文件,重新运行启动脚本,再用基岩版就可以通过域名和端口登录了

转发服务器后台的输出
基岩版登录java版账号的界面

关于登录的账号

  • 如果java服务器和Geyser的配置文件设置为离线登录,则登录使用的用户名是基岩版的用户名(Xbox昵称),等同于用java版客户端使用这个ID离线登录服务器。
  • 如果Geyser的配置文件设置为正版登录,不论java服务器是否设置正版登录,登录使用的用户名都是这个正版账号所对应的ID,基岩版的用户名对其无影响,等同于用java版客户端使用账号和密码正版登录服务器。

现有版本遇到的bug

基岩版登录仍有一些bug,不过相比于早期一些帖子中所描述的,已经修复了很多致命bug,可以有限制的正常游玩了。

  • 2020-05-12 java服务器:1.15.2PaperSpigot
    基岩客户端:1.14.6005.0Win10 Geyser:#140
    • 金色生命值和氧气值不显示
    • 鞘翅无法用火箭加速
    • 下界基岩以上的方块无法显示
    • 附魔台UI无法打开
    • 偶尔会卡不完整方块
    • 无法坐上船和矿车等
    • 睡觉不会显示动画(能跳过黑夜)
    • 个别粒子显示错误,显示为其他粒子

C++STL之unordered_map用法简析,从造轮子到用轮子

unordered_map是C++11中加入的,以哈希表为索引方式的STL结构。与map不同,unordered_map寻找索引的值的理论时间复杂度仅为O(1),而依靠红黑树的map是O(logn)。

要理解unordered_map的运作原理,首先来造个轮子,写个自己的哈希表寻址结构。

Hash值是每个数据某个数据(比如是key)通过运算得到的某个数值,将该数据放进整个结构(比如数组)中以这个Hash值为索引的地址中,就类似于把数据倒入桶中。当需要找到某个key值对应的数据时,也同样算出Hash值,然后直接在结构中寻找就可以。由于数组的地址连贯性,Hash值作为索引可以直接计算出数据所在的地址,因此时间复杂度仅为O(1)。

造个Hash Table试试

首先是用到的数据的结构Record:

class Record
{
private:
	int key;
	int value;
public:
	int the_key() { return key; }
	int the_value() { return value; }
	Record() { key = value = -1; }
	Record(int k, int v) : key(k), value(v) {}
	bool operator==(Record r) { return the_value() == r.the_value(); } //相等
	Record operator=(Record r); //赋值构造函数
	//...以及更多需要的函数
};

定义好了key和value,写好构造函数并且重载部分需要的操作符(具体略)。然后是利用Hash值寻址的结构hash_table。

enum Error_code { not_present, overflow, deplicate_error, success };
const int hash_size = 100;
class hash_table
{
private:
	Record table[hash_size];
	int hash(Record r); //获得某个Record的Hash值
	bool is_empty(int index) { return table[index].the_key() == -1; } //查询table数组中index位上是否已经有数据
public:
	hash_table();
	hash_table(const hash_table& ht);
	//...以及更多构造函数
	Error_code insert(const Record& r); //插入某个Record的函数
	Error_code retrive(const int& key, Record& r); //查询表中是否存在某个key值,并且存在r中
	Error_code remove(const int& key); //删去该key值对应的Record
	Error_code find_key(int value, int& result); //寻找第一个value匹配key
	Error_code find_value(int key, int& result); //寻找key对应的value
	//...以及更多增删查改的操作
	hash_table operator=(const hash_table& ht); //赋值构造函数
	//...以及更多重载运算符 
};

其中,灵魂部分便是hash(Record r),这个函数对r的key计算得到其Hash值,后面的函数中,增删查改等所有需要从key来寻找到地址的操作,都需要用到这个函数。

例:用取余运算作为Hash函数

//简单的采用取余得到的结果作为Hash值
int hash_table::hash(Record r) 
{ 
	return r.the_key() % hash_size; 
}
//每次insert一个Record,便先算出其hash值,然后根据索引存储数据
Error_code hash_table::insert(const Record& r)
{
	for (int index = hash(r), k = 0; k < hash_size; (index = (index == hash_size - 1) ? 0 : index + 1), k++)
	{
		if (is_empty(index))
		{
			table[index] = r;
			return success;
		}
	}
	return overflow;
}
//通过key寻找value也同样先算出Hash值,载根据索引查询数据
Error_code hash_table::find_value(int key, int& result)
{
	for (int index = hash(Record(key, 0)); index < hash_size; index++)
	{
		if (is_empty(index))
		{
			return not_present;
		}
		if (table[index].the_key() == key)
		{
			result = table[index].the_value();
			return success;
		}
	}
}
//...以及更多函数

这里需要注意的一点是,当数据发生冲突,即Hash值相等时,这里采用的办法是从这个地址开始不断向后寻找下一个可以存储数据的地址,然后存下,如果全满则返回overflow;取值的时候也类似。这种处理冲突的办法称为开放寻址法。

Unordered_map之用法

声明

像其他STL一样,unordered_map已经内置了很多方法;不过,它还可以传入更多的参数,先看看其定义

template < class Key,                  // unordered_map::key_type
           class T,                    // unordered_map::mapped_type
           class Hash = hash<Key>,     // unordered_map::hasher
           class Pred = equal_to<Key>, // unordered_map::key_equal
           class Alloc = allocator< pair<const Key,T> >  // unordered_map::allocator_type
           > class unordered_map;

第三到第五个参数都可以省略。第一个参数是Key值,第二个参数是存储的数据,第五个参数是空间配置器,没必要修改。这里聊聊第三第四两个参数。
其中,第三个参数需要一个包含取Hash值的函数,取的对象是第一个参数,即为数据的key值。这里依然以取余运算为Hash函数为例。

struct my_hash
{
	int operator()(const int& value) const
	{
		return value % hash_len;
	}
};

struct就是默认为public的class。为了简便,直接重载()运算符,这样,每个my_hash的对象都可以相当于一个函数名,用()传入参数,调用取Hash值的函数。
接下来是第四个参数,它需要包含一个判断key值是否相等的函数。

struct my_compare
{
	bool operator()(const int& x, const int& y) const
	{
		return x == y;
	}
};

也同样的道理,重载()运算符即可。
有了这样自定义好的两个类,便可以创建unordered_map了。

unordered_map<int, int, my_hash, my_compare> umap;
//声明了一个key值为int,数据也是int,取Hash值的方法的类为my_hash,判断key值是否相等的方法的类为my_compare的unordered_map

当然,这个例子中的my_hash和my_compare也是可以省略的,因为int型是可以直接比较的,默认的比较函数可以工作;unordered_map也内置了计算Hash值的方法。

方法

首先,键值对在unordered_map中的每个元素是pair<const Key, T>的模板类的实例化的对象,每一个pair中first属性是其key,second属性是其value。

另外,后一个insert或emplace入的的同key元素将被忽略,不会覆盖原有的value

  1. unordered_map::begin, end, cbegin, cend 头迭代器,超尾迭代器,const头迭代器,const超尾迭代器
  2. unordered_map::operator= 赋值构造函数,可以传入另一个unordered_map;移动构造函数,传入一个unordered_map右值;初始化列表,用直接量的列表赋值
  3. unordered_map::operator[] 其行为类似数组,以key为索引,可以读写值
    um3[“z”] = 5;
    um3[“y”] = um3[“z”];
  4. unordered_map::insert 插入一个或多个键值对
    um.insert(pair<string, int>{ “a”, 5 }); //使用直接量
    um.insert({ “a”, 5 }); //省略类型
    um2.insert(um.begin(), um.end()); //使用迭代器
  5. unordered_map::emplace 传入参数列表,自动创建一个键值对
    um.emplace( “c”, 10 ); //添加键值对pair<string, int>{ “c”, 10 }
  6. unordered_map::emplace_hint 传入一个迭代器和参数列表,自动(优先从该迭代器的位置)创建一个键值对,并且当成功插入时,返回指向插入元素的迭代器;因为key已存在而插入失败时,返回指向该key所在元素的迭代器(值不会覆盖)
    um.emplace_hint(um.begin(), “a”, 10); //返回指向{ “a”, 5 }的迭代器
  7. unordered_map::at 获得传入key对应的值
    um.at(“a”); //返回5
  8. unordered_map::find 寻找传入key对应的迭代器
    um.find(“a”); //返回指向pair<string, int>{ “a”, 5 }的迭代器
    um.find(“b”); //key不存在,返回um.end()
  9. unordered_map::erase 删去容器中的部分元素,可以传入key的值、某个迭代器、或者两个迭代器组成的范围
    um2.erase(um2.begin(), um2.end()); //这个例子相当于clear
  10. unordered_map::clear 清空容器
  11. unordered_map::swap 传入另一个unordered_map,交换两个容器的值
  12. unordered_map::empty 返回容器是否为空的布尔值
  13. unordered_map::count 计算传入的key在容器中存在的个数;事实上因为key是唯一的,只能得到0或1
    um.count(“a”); //返回1
    um.count(“b”); //返回0
  14. unordered_map :: hash_function 返回该容器使用的Hash函数的对象(可以当做函数指针使用)
    auto fn = um.hash_function();
    fn(“d”); //返回3775669363
  15. unordered_map :: key_eq 无参数,返回一个需要传入两个参数的函数,给该函数传入两个key,返回两个key是否Hash值相等的布尔值
    um.key_eq()(“a”, “A”); //返回false
  16. unordered_map::bucket 获得传入的key所在的桶的编号,传入的key不一定要在容器中已存在
    um.bucket(“a”); //返回4
    um.bucket(“b”); //返回5
  17. unordered_map::bucket_count 返回容器的桶的个数
    um.bucket_count(); //返回8
  18. unordered_map::bucket_size 传入一个unsigned int,获得这个编号的桶内的元素数
    um.bucket_size(4); //返回1
    um.bucket_size(5); //返回0
  19. unordered_map::size, max_size, load_factor, max_load_factor 该容器的元素个数,最大元素个数,已加载的桶的比例,最大加载的桶的比例,其中,load_factor = size / bucket_count
  20. unordered_map::reserve 传入一个unsigned int,将容器中的bucket_count设置为最适合的包含至少n个元素的大小
  21. unordered_map :: rehash 传入一个unsigned int,将容器中的bucket_count设置为n(或更多)
  22. unordered_map::equal_range 传入一个key,返回寻找到含有这个key的键值对所组成一个范围。返回值的first属性是头键值对,second属性是尾键值对。因为key是唯一的,返回的范围自然也只有一个元素,该方法在unordered_multimap中更常用。
    auto range = um.equal_range(“a”);
    for_each( range.first, range,second, [](auto x) {cout << x.first << x.second; } //输出a5
    这里使用了for_each语句,给定头尾和执行的函数,并且用Lambda表达式作为匿名函数,简单实现将range中所有元素(只有一个)进行输出
    其中x的类型是unordered_map::value_type
  23. unordered_map::get_allocator 返回allocator_type

参考了 http://www.cplusplus.com/reference/unordered_map/

链表解题笔记

刷完了Leetcode所有的链表简单—中等题,归纳一下用过的技巧。

一、快慢指针

相位差快慢

例题:实现一种算法,找出单向链表中倒数第 k 个节点。返回该节点的值。

class Solution {
public:
    int kthToLast(ListNode* head, int k) {
        ListNode* fast = head, *slow = head;
        for(int i = 0; i < k - 1; i++)
        {
            fast = fast->next;
        }
        while(fast->next != NULL)
        {
            fast = fast->next;
            slow = slow->next;
        }
        return slow->val;
    }
};

先让快指针走k-1步,再让快慢指针同速度前进。当快指针走到尾部,慢指针自然在倒数第k个节点。

步长快慢

例题:给定一个带有头结点 head 的非空单链表,返回链表的中间结点。如果有两个中间结点,则返回第二个中间结点。

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        if(head == NULL)
        {
            return NULL;
        }
        ListNode* fast = head;
        ListNode* low = head;
        while(fast->next != NULL)
        {
            low = low->next;
            fast = fast->next->next;
            if(fast == NULL)
            {
                break;
            }
        }
        return low;
    }
};

让快慢指针同时从头指针出发,快指针一次走两步,慢指针一次走一步,当快指针到达尾部,慢指针自然在正中间。

二、缓冲区

也就是另外建立存储数据的区域,例题:编写代码,移除未排序链表中的重复节点。保留最开始出现的节点。

class Solution {
public:
    ListNode* removeDuplicateNodes(ListNode* head) {
        ListNode* cur = head, *prev;
        int data[20001] = {0};
        while(cur != NULL)
        {
            if(data[cur->val] == 0)
            {
                data[cur->val]++;
                prev = cur;
                cur = cur->next;
            }
            else if(data[cur->val] == 1)
            {
                prev->next = cur->next;
                delete cur;
                cur = prev->next;
            }
        }
        return head;
    }
};

这里将每个数据放入对应的桶中,如果桶中已经有数据,自然判断出重复。

三、使用STL

同样也是使用了缓冲区,不过stl的一些方法可以大大简便操作

使用vector

例题:给定一个单链表 L:L0→L1→…→Ln-1→Ln ,
将其重新排列后变为: L0→Ln→L1→Ln-1→L2→Ln-2→…
你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。

class Solution {
public:
        void reorderList(ListNode* head) {
            if (!head) return;
            vector<ListNode*> vec;
            ListNode* cur = head;

            while (cur) {
                vec.push_back(cur);
                cur = cur->next;
            }

            int left = 0;
            int right = vec.size() - 1;
            while (left < right) {
                vec[left]->next = vec[right];
                vec[right--]->next = vec[++left];
            }
            vec[left]->next = nullptr;
        }
};

vector简便了取未操作过的首、尾节点的方法

使用stack

例题:多级双向链表中,除了指向下一个节点和前一个节点指针之外,它还有一个子链表指针,可能指向单独的双向链表。这些子列表也可能会有一个或多个自己的子项,依此类推,生成多级数据结构。给你位于列表第一级的头节点,请你扁平化列表,使所有结点出现在单级双链表中。

class Solution {
public:
    Node* flatten(Node* head) {
        if (!head) return head;
        stack<Node*> n;
        Node* p = head, *temp;
        while (true)
        {
            while(true)
            {
                if (p->child)
                {
                    if (p->next)
                        n.push(p->next);
                    p->next = p->child;
                    p->next->prev = p;
                    p->child = NULL;
                }
                if(!(p->next))
                    break;
                p = p->next;
            }
            if (n.empty())
                break;
            temp = p;
            p = n.top();
            n.pop();
            temp->next = p;
            p->prev = temp;
        }
        return head;
    }
};

使用了stack保证了后进先出,使得扁平化从最分支到主枝进行。

使用map

map确保了键值对的唯一性,可以快速解决重复值问题。例题:给你一个链表的头节点 head,请你编写代码,反复删去链表中由 总和 值为 0 的连续节点组成的序列,直到不存在这样的序列为止。删除完毕后,请你返回最终结果链表的头节点。

class Solution {
public:
    ListNode* removeZeroSumSublists(ListNode* head) {
        map<int, ListNode*> map;
        int sum = 0;
        ListNode* dummy = new ListNode(0), *cur = dummy;
        dummy->next = head;
        while (cur)
        {
            sum += cur->val;
            map[sum] = cur;
            cur = cur->next;
        }
        for(cur = dummy, sum = 0; cur; cur = cur->next)
        {
            sum += cur->val;
            if (map.find(sum) != map.end())
                cur->next = map[sum]->next;
        }
        return dummy->next;
    }
};

从头开始计算每到达一个节点时,前面所有节点值的总和,并且存在map中,如果有一个序列和为0,那么必有两个总和相等。再一次遍历时,如果某个总和在map中但不是当前节点,那么map中对应的节点和当前节点之间的和必定是0.

四、递归

链表的节点是相似的,可以使用递归解决。例题:给定单向链表的头指针和一个要删除的节点的值,定义一个函数删除该节点。返回删除后的链表的头节点。

class Solution {
public:
    ListNode* deleteNode(ListNode* head, int val) {
        if(!head) return NULL;
        if(head->val == val) return head->next;
        head->next = deleteNode(head->next,val);
        return head;
    }
};

通过递归,从头结点开始,下一个节点等于删除的只便跳过,重新连接链表。

五、补齐链表

当操作的两个链表长度不等时,可以先补齐至相同长度再操作。

例题:给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。你可以假设除了数字 0 之外,这两个数字都不会以零开头。

void addLinkList(struct ListNode* l1, struct ListNode* l2,int *cout)
{       
        if(l1==NULL||l2==NULL)
            return;
        if(l1->next!=NULL&&l2->next!=NULL)
            addLinkList(l1->next,l2->next,cout);
        int Sum=l1->val+l2->val+*cout;
        if(Sum>=10)
        {
            *cout=1;
            l1->val=Sum%10;
        }
        else
        {
            *cout=0;
            l1->val=Sum;
        }
        return;
}

六、原地修改

当复制的链表具有其他信息,不便于直接复制时,可以先原地复制,再间隔地挑出来。

例题:请实现 copyRandomList 函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链表中的任意节点或者 null。

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(!head) return NULL;
        Node* cur = head, *prev, *newhead;
        while(cur)
        {
            Node* newNode = new Node(cur->val);
            newNode->random = cur->random;
            newNode->next = cur->next;
            cur->next = newNode;
            cur = cur->next->next;
        }
        prev = head;
        newhead = head->next;
        while(prev)
        {
            cur = prev->next;
            if(cur->random)
                cur->random = cur->random->next;
            prev = prev->next->next;
        }
        prev = head;
        while(prev)
        {
            cur = prev->next;
            prev->next = prev->next->next;
            prev = prev->next;
            cur->next = prev ? prev->next : NULL;
        }
        return newhead;
    }
};

七、结合其他算法

例如结合BFS、DFS等搜索办法,DP、DC等优化算法等等