今天听说反转单链表,于是博主就自己想了想。
顾名思义,反转单链表,就是让一个单链表反向。 反转一个单链表,最容易想到的思路就是:
方法一
牺牲空间。 此方法没什么可说的,直接创建一个新的链表,倒序将上一个链表的各个节点拷贝到新链表中,并释放原链表。值得注意的是,如果直接拷贝各个节点,显然复杂度较高,因为拷贝最后一个节点时需要先指向最后一个节点,而指向最后一个节点是需要话时间的。因此可以先开辟一个lenth()长度的数组,将各节点先存入数组中,再使用反序索引来创建新的反转单链表。
接下来容易想到的方法则是使用三个节点指针来进行操作。
##方法二
先让两个节点指针p和q配合使两个节点的指向反向,同时用current记录剩下的链表。博主以前曾实现过一个模版链表,因此就在此基础上继续完善该链表。
|
|
继续思考,发现其实可以不用这么麻烦,如果从第2个节点开始,依次将节点插入到头节点之后,最后将第一个节点插到表尾。
方法三
不说了,直接上代码。
|
|