算法导论 O(n)时间内反转单链表_write a nonrecursive procedure to reverse a singly

算法导论 O(n)时间内反转单链表

1. 算法导论原题

Give a O(n) time nonrecursive procedure that reverses a singly linked list of n elements. The procedure should use no more than constant storage beyond that needed for thelist itself.
译：实现一个时间复杂度为O(n)的非递归过程反转一个有n个元素的单链表。这个过程应该使用常量的储存空间（除了链表本身）。

2. 如何在O(n)时间内反转单链表？

由于是单链表，想要在O(n)时间内反转单链表，就不可能遍历整个链表到后面的结点来跟前面结点交换数据。因此我们能做的，就是改变链表每一个结点的指针指向为前一个结点。我们需要用三个结点的储存空间：上一个结点、当前结点、下一个结点。首先将当前结点的下一个结点保存（因为下一步要改变当前结点的下一个结点），然后将当前结点指向上一个结点，再将当前结点保存到上一个结点，最后将当前结点移动到刚刚保存的下一个结点。题目没有说是用循环单链表，但是循环单链表和普通单链表它们的存储空间和O(n)时间内反转实现原理是一样的，所以我这里直接用循环单链表就行了。

3. 主要代码实现（C++）

template<typename ElemType>
bool CircularSinglyLink<ElemType>::Reverse()
{
    Node<ElemType>* pPrevNode = m_pHeadNode;
    Node<ElemType>* pCurrentNode = m_pHeadNode->GetNext(); 
    while(pCurrentNode != m_pHeadNode)
    {
        Node<ElemType>* nextNode = pCurrentNode->GetNext();
        pCurrentNode->SetNext(pPrevNode);
        pPrevNode = pCurrentNode;
        pCurrentNode = nextNode;
    }
    m_pHeadNode->SetNext(pPrevNode);
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

4. 完整代码实现（C++）

//CircularSinglyLink.h
#pragma once

#include <assert.h>
#include <stdio.h>

template<typename ElemType>
class Node
{
public:
    Node(Node<ElemType>* pNext = NULL, ElemType* pData = NULL);
    ElemType const& GetData() const;
    void SetData(ElemType val) ;
    Node<ElemType>* const& GetNext() const;
    void SetNext(Node<ElemType>* val);
private:
    ElemType* m_pData;
    Node<ElemType>* m_pNext;
};

template<typename ElemType>
class CircularSinglyLink
{
public:
    CircularSinglyLink();
    unsigned int const& GetLength() const;
    bool Insert(ElemType elem, unsigned int pos);
    bool InsertByPosNode(ElemType elem, Node<ElemType>* posNode, Node<ElemType>** RetInsetNode = NULL);
    bool Delete(unsigned int pos, ElemType* elem);
    bool Search(unsigned int pos, ElemType* elem) const;
    bool Visit(ElemType* elem, const unsigned int& pos) const;
    bool Empty();
    Node<ElemType>* HavaHeadNode();
    bool Reverse();
private:
    Node<ElemType>* m_pHeadNode;
    unsigned int m_length;
};

//————————————————————————————————//Node类的实现
template<typename ElemType>
Node<ElemType>::Node(Node<ElemType>* pNext /*= NULL*/, ElemType* pData /*= NULL*/)
    :m_pNext(pNext),m_pData(pData)
{

}


template<typename ElemType>
void Node<ElemType>::SetNext(Node<ElemType>* val)
{
    m_pNext = val;
}

template<typename ElemType>
Node<ElemType>* const& Node<ElemType>::GetNext() const
{
    return m_pNext;
}

template<typename ElemType>
void Node<ElemType>::SetData(ElemType val)
{
    m_pData = val;
}

template<typename ElemType>
ElemType const& Node<ElemType>::GetData() const
{
    return *m_pData;
}

//————————————————————————————————//CircularSinglyLink类实现

template<typename ElemType>
CircularSinglyLink<ElemType>::CircularSinglyLink()
    :m_pHeadNode(new Node<ElemType>()),m_length(0)
{
    m_pHeadNode->SetNext(m_pHeadNode);
}



template<typename ElemType>
bool CircularSinglyLink<ElemType>::InsertByPosNode(ElemType elem, Node<ElemType>* posNode, Node<ElemType>** RetInsetNode /*= NULL*/)
{
    Node<ElemType>* insertNode = new Node<ElemType>(posNode->GetNext(),new ElemType(elem));
    posNode->SetNext(insertNode);
    ++m_length;
    *RetInsetNode = insertNode;
    return true;
}


template<typename ElemType>
bool CircularSinglyLink<ElemType>::Insert(ElemType elem, unsigned int pos)
{
    if (pos > GetLength() || pos < 0)
    {
        assert(false && "Error: SinglyLink's insert pos is out of range!\n");
        return false;
    }

    for(Node<ElemType>* pCurrentNode = m_pHeadNode; pCurrentNode != NULL; pCurrentNode = pCurrentNode->GetNext())
    {
        if (pos-- == 0)
        {
            Node<ElemType>* insertNode = new Node<ElemType>(pCurrentNode->GetNext(),new ElemType(elem));
            pCurrentNode->SetNext(insertNode);
            ++m_length;
            return true;
        }
    }
    assert(false && "Error: SinglyLink Insert failed for unknow reason!");
    return false;
}

template<typename ElemType>
bool CircularSinglyLink<ElemType>::Delete(unsigned int pos, ElemType* elem)
{
    if (pos >= GetLength() || pos < 0)
    {
        assert(false && "Error: SinglyLink's delete pos is out of range!\n");
    }

    for(Node<ElemType>* pCurrentNode = m_pHeadNode; pCurrentNode != NULL; pCurrentNode = pCurrentNode->GetNext())
    {
        if (pos-- == 0)
        {
            Node<ElemType>* deleteNode = pCurrentNode->GetNext();
            pCurrentNode->SetNext(deleteNode->GetNext());
            *elem = deleteNode->GetData();
            delete deleteNode;
            --m_length;
            return true;
        }
    }
    assert(false && "Error: SinglyLink pos delete failed for unknow reason!");
    return false;
}

template<typename ElemType>
unsigned int const& CircularSinglyLink<ElemType>::GetLength() const
{
    return m_length;
}

template<typename ElemType>
bool CircularSinglyLink<ElemType>::Search(unsigned int pos, ElemType* elem) const
{
    if (pos >= GetLength() || pos < 0)
    {
        assert(false && "Error: SinglyLink's search pos is out of range!\n");
    }

    for(Node<ElemType>* pCurrentNode = m_pHeadNode; pCurrentNode != NULL; pCurrentNode = pCurrentNode->GetNext())
    {
        if (pos-- == 0 && (pCurrentNode->GetNext() != NULL) )
        {
            *elem = pCurrentNode->GetNext()->GetData();
            return true;
        }
    }

    return false;
}

template<typename ElemType>
bool CircularSinglyLink<ElemType>::Visit(ElemType* elem, const unsigned int& pos) const
{
    if (pos >= GetLength() || pos < 0)
    {
        return false;
    }
    return Search(pos,elem);
}

template<typename ElemType>
bool CircularSinglyLink<ElemType>::Empty()
{
    return !m_length;
}

template<typename ElemType>
Node<ElemType>* CircularSinglyLink<ElemType>::HavaHeadNode()
{
    return m_pHeadNode;
}


template<typename ElemType>
bool CircularSinglyLink<ElemType>::Reverse()
{
    Node<ElemType>* pPrevNode = m_pHeadNode;
    Node<ElemType>* pCurrentNode = m_pHeadNode->GetNext(); 
    while(pCurrentNode != m_pHeadNode)
    {
        Node<ElemType>* nextNode = pCurrentNode->GetNext();
        pCurrentNode->SetNext(pPrevNode);
        pPrevNode = pCurrentNode;
        pCurrentNode = nextNode;
    }
    m_pHeadNode->SetNext(pPrevNode);
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206

//Util.h
#pragma once

namespace Util
{
    template<typename T>
    void PrintMemory(const T& dateStruct, unsigned int size)
    {
        cout << "PrintMemory: ";
        for (int i = 0; i != size; i++)
        {
            ElemType tempElem;
            if (!dateStruct.Visit(&tempElem,i))
            {
                printf("\n");
                return;
            }
            printf("%d ",tempElem);
        }
        printf("\n");
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

//main.cpp
#include "Util.h"
#include "CircularSinglyLink.h"
#include <iostream>

using namespace std;

typedef int ElemType;

int main()
{
    CircularSinglyLink<int> testCircularSinglyLink;

    for (int i = 0; i != 5; i++)
    {
        testCircularSinglyLink.Insert(i+1,i);
    }

    cout << "testCircularSinglyLink:\n";
    Util::PrintMemory(testCircularSinglyLink,testCircularSinglyLink.GetLength());

    cout << "\nReverse testCircularSinglyLink...\n";
    testCircularSinglyLink.Reverse();

    cout << "\ntestCircularSinglyLink:\n";
    Util::PrintMemory(testCircularSinglyLink,testCircularSinglyLink.GetLength());

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

5. 程序运行结果

testCircularSinglyLink:
PrintMemory: 1 2 3 4 5

Reverse testCircularSinglyLink…

testCircularSinglyLink:
PrintMemory: 5 4 3 2 1