反转单链表
Changkun Ou
·
2013-09-24
·
via Posts on Changkun's Blog
今天听说反转单链表，于是博主就自己想了想。
顾名思义，反转单链表，就是让一个单链表反向。
反转一个单链表，最容易想到的思路就是：
方法一
牺牲空间。
此方法没什么可说的，直接创建一个新的链表，倒序将上一个链表的各个节点拷贝到新链表中，并释放原链表。值得注意的是，如果直接拷贝各个节点，显然复杂度较高，因为拷贝最后一个节点时需要先指向最后一个节点，而指向最后一个节点是需要话时间的。因此可以先开辟一个lenth()长度的数组，将各节点先存入数组中，再使用反序索引来创建新的反转单链表。
接下来容易想到的方法则是使用三个节点指针来进行操作。
##方法二
先让两个节点指针p和q配合使两个节点的指向反向，同时用current记录剩下的链表。博主以前曾实现过一个模版链表，因此就在此基础上继续完善该链表。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
template <class T>
void Chain<T>::reversal()
{
ChainNode *p = head;
ChainNode *q = head->next;
ChainNode *current;
head->next = NULL;
while(q){
current = q->next; // current用于纪录剩余的链表
q->next = p;
p = q;
q = current;
}
head = p; // 记得修改head，否则按head输出仅输出了最后一个节点
}
|
继续思考，发现其实可以不用这么麻烦，如果从第2个节点开始，依次将节点插入到头节点之后，最后将第一个节点插到表尾。
方法三
不说了，直接上代码。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
template <class T>
void Chain<T>::reversal_2()
{
ChainNode* p;
ChainNode* q;
p = head->next;
while(p->next != NULL){
q = p->next;
p->next = q->next;
q->next = head->next;
head->next = q;
}
p->next = head; // 相当于成环
head = p->next->next; // 新head变为原head的next
p->next->next = NULL; // 断掉环
}
|
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。
