本文共 6249 字，大约阅读时间需要 20 分钟。
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个元素的单链表。这个过程应该使用常量的储存空间（除了链表本身）。
由于是单链表，想要在O(n)时间内反转单链表，就不可能遍历整个链表到后面的结点来跟前面结点交换数据。因此我们能做的，就是改变链表每一个结点的指针指向为前一个结点。我们需要用三个结点的储存空间：上一个结点、当前结点、下一个结点。首先将当前结点的下一个结点保存（因为下一步要改变当前结点的下一个结点），然后将当前结点指向上一个结点，再将当前结点保存到上一个结点，最后将当前结点移动到刚刚保存的下一个结点。题目没有说是用循环单链表，但是循环单链表和普通单链表它们的存储空间和O(n)时间内反转实现原理是一样的，所以我这里直接用循环单链表就行了。
templatebool CircularSinglyLink ::Reverse(){ Node * pPrevNode = m_pHeadNode; Node * pCurrentNode = m_pHeadNode->GetNext(); while(pCurrentNode != m_pHeadNode) { Node * nextNode = pCurrentNode->GetNext(); pCurrentNode->SetNext(pPrevNode); pPrevNode = pCurrentNode; pCurrentNode = nextNode; } m_pHeadNode->SetNext(pPrevNode); return true;}
//CircularSinglyLink.h#pragma once#include#include template class Node{public: Node(Node * pNext = NULL, ElemType* pData = NULL); ElemType const& GetData() const; void SetData(ElemType val) ; Node * const& GetNext() const; void SetNext(Node * val);private: ElemType* m_pData; Node * m_pNext;};template class CircularSinglyLink{public: CircularSinglyLink(); unsigned int const& GetLength() const; bool Insert(ElemType elem, unsigned int pos); bool InsertByPosNode(ElemType elem, Node * posNode, Node ** 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 * HavaHeadNode(); bool Reverse();private: Node * m_pHeadNode; unsigned int m_length;};//————————————————————————————————//Node类的实现template Node ::Node(Node * pNext /*= NULL*/, ElemType* pData /*= NULL*/) :m_pNext(pNext),m_pData(pData){}template void Node ::SetNext(Node * val){ m_pNext = val;}template Node * const& Node ::GetNext() const{ return m_pNext;}template void Node ::SetData(ElemType val){ m_pData = val;}template ElemType const& Node ::GetData() const{ return *m_pData;}//————————————————————————————————//CircularSinglyLink类实现template CircularSinglyLink ::CircularSinglyLink() :m_pHeadNode(new Node ()),m_length(0){ m_pHeadNode->SetNext(m_pHeadNode);}template bool CircularSinglyLink ::InsertByPosNode(ElemType elem, Node * posNode, Node ** RetInsetNode /*= NULL*/){ Node * insertNode = new Node (posNode->GetNext(),new ElemType(elem)); posNode->SetNext(insertNode); ++m_length; *RetInsetNode = insertNode; return true;}template bool CircularSinglyLink ::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 * pCurrentNode = m_pHeadNode; pCurrentNode != NULL; pCurrentNode = pCurrentNode->GetNext()) { if (pos-- == 0) { Node * insertNode = new Node (pCurrentNode->GetNext(),new ElemType(elem)); pCurrentNode->SetNext(insertNode); ++m_length; return true; } } assert(false && "Error: SinglyLink Insert failed for unknow reason!"); return false;}template bool CircularSinglyLink ::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 * pCurrentNode = m_pHeadNode; pCurrentNode != NULL; pCurrentNode = pCurrentNode->GetNext()) { if (pos-- == 0) { Node * 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 unsigned int const& CircularSinglyLink ::GetLength() const{ return m_length;}template bool CircularSinglyLink ::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 * pCurrentNode = m_pHeadNode; pCurrentNode != NULL; pCurrentNode = pCurrentNode->GetNext()) { if (pos-- == 0 && (pCurrentNode->GetNext() != NULL) ) { *elem = pCurrentNode->GetNext()->GetData(); return true; } } return false;}template bool CircularSinglyLink ::Visit(ElemType* elem, const unsigned int& pos) const{ if (pos >= GetLength() || pos < 0) { return false; } return Search(pos,elem);}template bool CircularSinglyLink ::Empty(){ return !m_length;}template Node * CircularSinglyLink ::HavaHeadNode(){ return m_pHeadNode;}template bool CircularSinglyLink ::Reverse(){ Node * pPrevNode = m_pHeadNode; Node * pCurrentNode = m_pHeadNode->GetNext(); while(pCurrentNode != m_pHeadNode) { Node * nextNode = pCurrentNode->GetNext(); pCurrentNode->SetNext(pPrevNode); pPrevNode = pCurrentNode; pCurrentNode = nextNode; } m_pHeadNode->SetNext(pPrevNode); return true;}
//Util.h#pragma oncenamespace Util{ template 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"); }} //main.cpp#include "Util.h"#include "CircularSinglyLink.h"#includeusing namespace std;typedef int ElemType;int main(){ CircularSinglyLink 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;}
testCircularSinglyLink:
PrintMemory: 1 2 3 4 5Reverse testCircularSinglyLink…
testCircularSinglyLink:
PrintMemory: 5 4 3 2 1
转载地址：http://ziyii.baihongyu.com/