链表的遍历和反转

2018年3月25日17:33:48C/C++评论275字数 626阅读2分5秒阅读模式

一、链表的遍历

链表的遍历算是十分简单了，从头到尾获取next指针的值，如果next不为0，一直打印。

// 遍历链表，结果保存在vector中返回
template <typename T>
std::vector<T> CMyList<T>::traversal() const {
    vector<T> v;
    CListNode<T> *p = root.getNext();
    while (p)
    {
        v.push_back(p->getData());
        p = p->getNext();
    }

    return v;
}

// 遍历链表，结果保存在vector中返回

template <typename T>

std::vector<T> CMyList<T>::traversal() const {

vector<T> v;

CListNode<T> *p = root.getNext();

while (p)

{

v.push_back(p->getData());

p = p->getNext();

}

return v;

}

这是一个链表和双向链表都可以使用的打印方式，但是对于循环链表来说要注意起始节点。

二、链表反转

链表反转在面试中经常会考的问题，总结了一下共有一下几种方式：

修改链表指向实现。
使用栈实现。
递归实现

2.1 修改链表指向

修改节点的流程：

初始化节点，设置当前修改的节点cur为第一个节点root.getNext()。
如果当前指向的节点cur存在，向下执行修改，否则退出反转。
备份当前节点的下一个节点。
修改当前节点的下一个节点为上一个节点。
令cur指向备份的下一个节点，继续第二步。

// 通过修改节点指向反转链表
template<typename T>
inline void CMyList<T>::reverseByModifyNode() {
    CListNode<T> *pre, *cur, *next;
    pre = 0;
    next = 0;
    cur = root.getNext();
    while (cur) {
        // 备份当前节点的下一个节点
        next = cur->getNext();
        // 修改当前节点的next指向
        cur->setNext(pre);
        // 当前节点作为pre节点
        pre = cur;
        // 当前节点后移
        cur = next;
    }

    // cur = 0, next = 0, pre = 最后一个节点
    // 修改根节点的下一个指向
    root.setNext(pre);
}

// 通过修改节点指向反转链表

template<typename T>

inline void CMyList<T>::reverseByModifyNode() {

CListNode<T> *pre, *cur, *next;

pre = 0;

next = 0;

cur = root.getNext();

while (cur) {

// 备份当前节点的下一个节点

next = cur->getNext();

// 修改当前节点的next指向

cur->setNext(pre);

// 当前节点作为pre节点

pre = cur;

// 当前节点后移

cur = next;

}

// cur = 0, next = 0, pre = 最后一个节点

// 修改根节点的下一个指向

root.setNext(pre);

}

对于双向链表的反转也是一样，只是多了一个指针替换：

template <typename T>
void CDoubleList<T>::reverse()
{
    CListNode<T> *pre, *cur, *next;
    cur = root.getNext();
    pre = 0;
    while (cur) {
        // 备份next指针
        next = cur->getNext();
        // 指针反转
        cur->setNext(pre);
        cur->setPre(next);
        // 更新下一个节点
        pre = cur;
        cur = next;
    }
    // 更新头节点
    root.setPre(root.getNext());
    root.setNext(pre);
}

template <typename T>

void CDoubleList<T>::reverse()

{

CListNode<T> *pre, *cur, *next;

cur = root.getNext();

pre = 0;

while (cur) {

// 备份next指针

next = cur->getNext();

// 指针反转

cur->setNext(pre);

cur->setPre(next);

// 更新下一个节点

pre = cur;

cur = next;

}

// 更新头节点

root.setPre(root.getNext());

root.setNext(pre);

}

2.2 通过栈反转

栈的特点是先进后出，因此通过栈来反转是再合适不过了。

template<typename T>
inline void CMyList<T>::reverseByStack()
{
    CStack<T> s;
    CListNode<T> *p = root.getNext(), *pre;
    // 令根节点指向空
    root = 0;
    while (p) {
        // 备份节点
        pre = p;
        // 压栈
        s.push(p->getData());
        p = p->getNext();
        // 节点压栈后删除
        delete pre;
    }

    // 重新生成链表
    p = &root;
    while (!s.empty()) {
        p->setNext(new CListNode<T>(s.pop(), this));
        p = p->getNext();
    }
}

template<typename T>

inline void CMyList<T>::reverseByStack()

{

CStack<T> s;

CListNode<T> *p = root.getNext(), *pre;

// 令根节点指向空

root = 0;

while (p) {

// 备份节点

pre = p;

// 压栈

s.push(p->getData());

p = p->getNext();

// 节点压栈后删除

delete pre;

}

// 重新生成链表

p = &root;

while (!s.empty()) {

p->setNext(new CListNode<T>(s.pop(), this));

p = p->getNext();

}

2.3 通过递归反转

如果只需要反向打印列表，通过递归的方式反转也是相当简单，只是当链表过长时可能会导致内存溢出。

也可以直接通过这个方法逆向构造一个链表然后重新赋值root达到在当前对象上反转的目的，把vector改成一个链表对象每次都插入元素在最后。

template<typename T>
inline void CMyList<T>::reverseByVector(vector<T>& v) {
    reverseVector(v, root.getNext());
}


template<typename T>
inline void CMyList<T>::reverseVector(vector<T>& v, CListNode<T>* node) {
    if (!node) return;
    reverseVector(v, node->getNext());
    v.push_back(node->getData());
}