C言語で連結リストの末尾からn番目のノードを取得するプログラム

n個のノードからなる連結リストが与えられたとき、その末尾からn番目のノードを出力するのが本記事の目的です。プログラムはリスト内のノードの並び順を変更してはならず、あくまで末尾から数えてn番目に位置するノードの値を表示するだけでなければなりません。

具体例

入力 -: 10 20 30 40 50 60
　　N = 3
出力 -: 40

上記の例では、先頭ノードから順に「count − n」個目までのノード（10, 20, 30, 40, 50, 60）を走査し、末尾から3番目のノードとして 40 が得られます。

効率的なアプローチ

リスト全体を最後まで走査しなくても、以下の手順で目的のノードを見つけられます。

• ノード型の一時ポインタ（ここでは temp）を用意する
• temp を、head ポインタが指す先頭ノードに設定する
• カウンタをリスト内のノード総数に設定する
• 「count − n」回だけ temp を temp→next へ進める
• temp→data を表示する

たとえばノード数が6で n = 3 の場合、ループは「6 − 3 = 3」回繰り返されます。位置0の10から始まり、位置1の20、位置2の30、そして位置3の40に到達し、これが結果となります。この方法ならリスト全体を末尾まで辿る必要がなく、処理時間とメモリの両面で効率的です。

アルゴリズム

開始
Step 1 -> ノードの構造体を作成し、temp・next・head を構造体ノードへのポインタとして宣言する
    struct node
        int data
        struct node *next, *head, *temp
    終了
Step 2 -> リストにノードを挿入する関数を宣言する
    void insert(int val)
        struct node* newnode = (struct node*)malloc(sizeof(struct node))
        newnode->data = val
        IF head == NULL
            head = newnode に設定
            head->next = NULL に設定
        終了
        Else
            temp = head に設定
            Loop While temp->next != NULL
                temp = temp->next に設定
            終了
            newnode->next = NULL に設定
            temp->next = newnode に設定
        終了
Step 3 -> リストを表示する関数を宣言する
    void display()
        IF head == NULL
            「ノードなし」と表示
        終了
        Else
            temp = head に設定
            Loop While temp != NULL
                temp->data を表示
                temp = temp->next に設定
            終了
        終了
Step 4 -> 連結リストの末尾からn番目のノードを求める関数を宣言する
    void last(int n)
        int i を宣言
        temp = head に設定
        Loop For i = 0 and i < count - n and i++
            temp = temp->next に設定
        終了
        temp->data を表示
Step 5 -> main() 内での処理
    struct node* head = NULL としてノードを作成
    変数 n を 3 として宣言
    insert(10) を呼び出してノードを挿入
    display() を呼び出してリストを表示
    last(n) を呼び出して末尾からn番目のノードを求める
終了

C言語による実装例

#include<stdio.h>
#include<stdlib.h>
//ノードの構造体
struct node{
    int data;
    struct node *next;
}*head,*temp;
int count=0;
//リストにノードを挿入する関数
void insert(int val){
    struct node* newnode = (struct node*)malloc(sizeof(struct node));
    newnode->data = val;
    newnode->next = NULL;
    if(head == NULL){
        head = newnode;
        temp = head;
        count++;
    } else {
        temp->next=newnode;
        temp=temp->next;
        count++;
    }
}
//リストを表示する関数
void display(){
    if(head==NULL)
        printf("no node ");
    else {
        temp=head;
        while(temp!=NULL) {
            printf("%d ",temp->data);
            temp=temp->next;
        }
    }
}
//連結リストの末尾から3番目のノードを求める関数
void last(int n){
    int i;
    temp=head;
    for(i=0;i<count-n;i++){
        temp=temp->next;
    }
    printf("\n%drd node from the end of linked list is : %d" ,n,temp->data);
}
int main(){
    //リストの作成
    struct node* head = NULL;
    int n=3;
    //リストへの要素挿入
    insert(1);
    insert(2);
    insert(3);
    insert(4);
    insert(5);
    insert(6);
    //リストの表示
    printf("\nlinked list is : ");
    display();
    //末尾からn番目の要素を求める関数の呼び出し
    last(n);
    return 0;
}

実行結果

linked list is : 1 2 3 4 5 6
3rd node from the end of linked list is : 4

このように、ノード総数を管理しておけば「count − n」回のポインタ移動だけで目的のノードにアクセスできるため、シンプルかつ高速な実装が可能です。