Published at:   |   Reading: 590 words ~2min   |   PV/UV: /

今天听说反转单链表，于是博主就自己想了想。

顾名思义，反转单链表，就是让一个单链表反向。 反转一个单链表，最容易想到的思路就是：

方法一

牺牲空间。 此方法没什么可说的，直接创建一个新的链表，倒序将上一个链表的各个节点拷贝到新链表中，并释放原链表。值得注意的是，如果直接拷贝各个节点，显然复杂度较高，因为拷贝最后一个节点时需要先指向最后一个节点，而指向最后一个节点是需要话时间的。因此可以先开辟一个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; // 断掉环
}
0%