剣指Offer-6:エンドからチェーンテーブルを印刷

5348 ワード

剣指Offer 筆記試験の面接プログラミング問題アルゴリズムチェーン？メータースタック再帰する

タイトル:
チェーンテーブルを入力し、チェーンテーブルの各ノードの値を末尾から印刷します.
問題解決:
*チェーンテーブルは動的データ構造であり、値を検索するには、最初のノードから開始するしかありません.後進先出構造.
リンク:
剣指Offer(第2版):P 58
構想ラベル:
データ構造:チェーンテーブル、スタック、vector
アルゴリズム:再帰
回答:
1. C++

(1)は最初から最後まで出力が簡単で,ノードを反転させるポインタであると考えられる.しかし、元のチェーンテーブルの構造を破壊し、推奨しません.

(2)チェーンテーブルを最初から遍歴し、先にアクセスした後出力、後にアクセスした先出力、「後進先出」をスタックで実現する.

(3)再帰は本質的にスタックの構造であり、再帰を利用して実現することができる.しかし、チェーンテーブルが長い場合、再帰は関数呼び出しのレベルが深くなり、関数呼び出しスタックのオーバーフローを引き起こす可能性があるため、スタックを使用して実現することを推奨します.

スタックの実装:

/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/

class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        std::vector<int> values;
        std::stack nodes;

        ListNode* pNode = head;
        while(pNode != nullptr){
            nodes.push(pNode);
            pNode = pNode->next;
        }

        while(!nodes.empty()){
            pNode = nodes.top();
            values.push_back(pNode->val);
            nodes.pop();
        }

        return values;
    }
};

再帰実装:

class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        std::vector<int> values;

        if(head != nullptr){
            if(head->next != nullptr){
                printListFromTailToHead(head->next);
            }

            values.push_back(head->val);
        }

        return values;
    }
};

チェーンテーブルのその他の操作:

//          
void AddToTail(ListNode** pHead, int value){
    ListNode* pNew = new ListNode();
    pNew->val = value;
    pNew->next = nullptr;

    if (*pHead == nullptr){
        *pHead = pNew;
    }else{
        ListNode* pNode = *pHead;
        while(pNode->next != nullptr)
            pNode = pNode->next;

        pNode->next = pNew;
    }

    return;
}

//       value   
void RemoveNode(ListNode** pHead, int value){
    if(pHead == nullptr || *pHead == nullptr) return;

    ListNode* pToDeleted = nullptr;
    if((*pHead)->val == value){
        pToDeleted = *pHead;
        *pHead = (*pHead)->next;
    }else{
        ListNode* pNode = *pHead;
        while(pNode->next != nullptr && pNode->next->val != value)
            pNode = pNode->next;

        if(pNode->next != nullptr && pNode->next->val == value){
            pToDeleted = pNode->next;
            pNode->next = pNode->next->next;
        }
    }

    if(pToDeleted != nullptr){
        delete pToDeleted;
        pToDeleted = nullptr;
    }

    return;
}

C++関連:
チェーンテーブルの追加関数で、チェーンテーブルのポインタを指すポインタを使用する理由:

http://blog.csdn.net/shen_jz2012/article/details/50631317

クイックインデックスアルゴリズム

Python簡単なQRコード