链表版汉诺塔问题

c++代码

#include<iostream>

struct Node{
    int data;
    Node* next; 
};

class Stack{
  public:
    Stack(){
        top = 0;
    }
    
    ~Stack(){
        Node* next;
        while(top){
            next = top->next;
            delete top;
            top = next;
        }
    }
    
    void push(int d){
        Node* p = new Node;
        p->data = d;
        p->next = top;
        top = p;
    }
    
    int pop(){
        int d;
        Node* p = top;
        d = top->data;
        top = top->next;
        delete p;
        return d;
    }
    
    Node* top;
};

int count = 1;

Stack s[3];

void Hanoi(char A, char B, char C, int n){
    if (n == 0)
        return;
        
    int a = A - 'A';
    int c = C - 'A';
    
    Hanoi(A, C, B, n-1);
    std::cout<<count++<<":"<<A<<"->"<<C<<std::endl;
    s[c].push(s[a].pop());
    Hanoi(B, A, C, n-1);
}

int main(){
    char A, B, C;
    int n;
    std::cin>>A>>B>>C>>n;

    for(int i = n; i > 0; i--){
        s[0].push(i);
    }
    
    Hanoi(A, B, C, n);
    
    system("pause");
    return 0;
}

复杂度分析

• 空间
  按要求利用链表栈实现，应为O(n)

• 时间
  核心步骤是Hanoi函数的递归，次数看count即可，应为O(2^n)

---

有任何问题请回复提出。然后欢迎关注微信公众号格物致愚：

格物致愚