一、链表的遍历

链表的遍历算是十分简单了，从头到尾获取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;
}

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

二、链表反转

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

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

2.1 修改链表指向

修改节点的流程：

1. 初始化节点，设置当前修改的节点cur为第一个节点root.getNext()。
2. 如果当前指向的节点cur存在，向下执行修改，否则退出反转。
3. 备份当前节点的下一个节点。
4. 修改当前节点的下一个节点为上一个节点。
5. 令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>
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();
    }
}

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());
}