後ろからk番目

問題

単方向連結リストにおいて末尾から数えてk番目の要素を返す。

考え方

連結リストの長さがわからないという前提で考える。 ランナーテクニックを利用する。 ２つのポインタを用意する。

• 前からk番目からスタート
• 初めからスタート １つ目のポインタが最後に着くときに、２つ目のポインタがちょうど後ろからk番目にいることになる。

時間計算量はO(N).

コード例

// 単方向連結リスト
class Node{
public:
    Node* next;
    int data;
    Node(int d){
        data = d;
        next = NULL;
    }
    ~Node(){
        cout << "node消去" << endl;
    }
    void appendToTail(int d){
        Node* end = new Node(d);
        Node* n = this;
        while(n->next!=NULL){
            n = n->next;
        }
        n->next = end;
    }
};

// ポインタ用いて実装
Node* nthFromLast(Node* head, int k){
    Node* p1 = head;
    Node* p2 = head;
    for(int i=0; i<k; i++){
        if(p1==NULL)return NULL;
        p1 = p1->next;
    }
    //--p1がnullまで進める
    while(p1!=NULL){
        p1 = p1->next;
        p2 = p2->next;
    }
    return p2;
}


int main(void){
    int i, k;
    k = 3;
    Node* node = new Node(10);
    for(i=0; i<10; i++){
        node->appendToTail(i);
    }

    Node* head = node;
    while(node!=NULL){
        cout << node->data << " -> ";
        node = node->next;
    }
    cout << endl;
    //--func---
    Node *ans;
    ans = nthFromLast(head, k);
    cout << "後ろから" << k << "番目は" << ans->data << endl;
    return 0;
}

参考

book.mynavi.jp