题目

用代码实现反转链表，要求：不能使用栈数据结构，时间复杂度O(n).

实现

• LinkList.h文件代码

#ifndef _LINKLIST_H_
#define _LINKLIST_H_

// 节点类, 使用了模板类,方便数据类型
template<class T>
class Node
{
public:
    T data;
    Node<T>* next;
public:
    Node(){}
    Node(T v, Node<T>* node)
    {
        this->data = v;
        this->next = node;
    }
};

template<class T>
class LinkList
{
private:
    Node<T>* head;
    Node<T>* tail;
    int count;
public:
    LinkList();
    ~LinkList();
    int size();
    void print();
    void append(T data);
    void reverse();
};

// 初始化链表
template<class T>
LinkList<T>::LinkList() : count(0)
{
    head = new Node<T>;
    head->next = NULL;
    tail = head;
    int length;
    cout << "请输入链表初始长度:";
    cin >> length;
    for (int i = 0; i < length; ++i)
    {
        T data;
        cout << "第" << (i + 1) << "个节点的内容:";
        cin >> data;
        append(data);
    }
}

template<class T>
LinkList<T>::~LinkList()
{
    Node<T>* node = head->next;
    Node<T>* tmp;
    while (node != NULL)
    {
        tmp = node;
        node = node->next;
        delete tmp;
    }
    delete head;
    head = NULL;
    tail = NULL;
}

// 返回链表的长度
template<class T>
int LinkList<T>::size()
{
    return count;
}

template <class T>
void LinkList<T>::print()
{
    Node<T>* node = head->next;
    while (node)
    {
        cout << node->data << "  ";
        node = node->next;
    }
    cout << endl;
}

template <class T>
void LinkList<T>::append(T data)
{
    Node<T>* node = new Node<T>();
    node->data = data;
    node->next = NULL;
    tail->next = node;
    tail = node;
    ++count;
}

template <class T>
void LinkList<T>::reverse()
{
    // 由于是带有头节点的链表，因此需要这两个条件
    if (head->next == NULL || head->next->next == NULL)
        return;
    Node<T>* current = head->next->next;
    tail = head->next;
    tail->next = NULL;
    while (current)
    {
        Node<T>* tmp = current->next;
        current->next = head->next;
        head->next = current;
        current = tmp;
    }
}
#endif

• main.cpp

#include <iostream>
#include "LinkList.cpp"
using namespace std;

int main()
{
    LinkList<int> list = LinkList<int>();
    cout << "链表结构内容:";
    list.print();
    list.reverse();
    cout << "链表反转后的结构：";
    list.print();
    system("pause");
    return 0;
}