โปรแกรมหาโหนดที่ n จากท้ายของ Linked List ในภาษา C

โจทย์

กำหนด Linked List ที่มี n โหนด ให้พิมพ์โหนดที่ n จากท้ายของ Linked List โดยไม่เปลี่ยนลำดับของโหนด

ตัวอย่าง

Input: 10 → 20 → 30 → 40 → 50 → 60, N = 3
Output: 40

อธิบาย: เริ่มจากโหนดแรก นับจากท้าย 3 โหนด คือ 40

วิธีการที่มีประสิทธิภาพ

แทนที่จะเดินผ่านทั้งลิสต์ ใช้วิธีนี้:

1. สร้าง pointer ชั่วคราว temp ชี้ที่โหนดแรก (head)
2. นับจำนวนโหนดทั้งหมด (count)
3. เลื่อน temp ไปที่ตำแหน่ง count - n
4. แสดงข้อมูลของ temp

วิธีนี้ประหยัดหน่วยความจำและเวลา เพราะไม่ต้องเดินจนจบลิสต์

อัลกอริทึม

1. สร้างโครงสร้างโหนด (struct node) มี data และ next pointer
2. ฟังก์ชัน insert() เพิ่มโหนดท้ายลิสต์
3. ฟังก์ชัน display() แสดงลิสต์ทั้งหมด
4. ฟังก์ชัน last(n) หาโหนดที่ n จากท้าย: วนลูป i=0 ถึง count-n เลื่อน temp = temp->next แล้วพิมพ์ temp->data
5. ใน main(): สร้างลิสต์ เรียก insert() หลายครั้ง เรียก display() และ last(3)

โค้ดภาษา 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;
        }
    }
}

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();
    last(n);
    return 0;
}

ผลลัพธ์

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