การพิมพ์ลิงก์ลิสต์ย้อนกลับโดยไม่ใช้พื้นที่เพิ่มและไม่แก้ไขในโปรแกรม C

งานคือพิมพ์โหนดเริ่มจากท้ายของลิงก์ลิสต์โดยไม่ใช้พื้นที่เพิ่ม หมายถึงไม่ควรมีตัวแปรเพิ่ม แต่จะย้ายหัวโหนดที่ชี้ไปโหนดแรก

ตัวอย่าง

Input: 10 21 33 42 89
Output: 89 42 33 21 10

มีหลายวิธีพิมพ์ลิงก์ลิสต์ย้อนกลับ เช่น เรียกซ้ำ (ใช้พื้นที่) ย้อนกลับลิงก์ลิสต์ (ต้องแก้ไข) ใช้สแต็ก (พื้นที่ O(n)) แต่วิธีเหล่านี้ใช้พื้นที่มากกว่า O(1)

เพื่อให้ได้ผลลัพธ์โดยไม่ใช้พื้นที่มากกว่า O(1) สามารถทำได้ดังนี้:

• นับจำนวนโหนดในลิงก์ลิสต์
• ลูปจาก i = n ถึง 1 และพิมพ์โหนดที่ตำแหน่ง i

อัลกอริทึม

START
Step 1 -> create node variable of type structure
  Declare int data
  Declare pointer of type node using *next
Step 2 -> Declare function int get(struct node* head)
  Declare variable as int count=0
  Declare struct node *newme=head
  Loop While newme!=NULL
    Increment count by 1
    Set newme = newme->next
  End
  Return count
Step 3 -> Declare Function void push(node** headref, char newdata)
  Allocate memory using malloc
  Set newnode->data = newdata
  Set newnode->next = (*headref)
  Set (*headref) = newnode
Step 4 -> Declare function int getN(struct node* head, int n)
  Declare struct node* cur = head
  Loop for int i=0; inext
  End
  Return cur->data
Step 5 -> Declare function void reverse(node *head)
  Declare int n = get(head)
  Loop For int i=n; i>=1; i--
    Print getN(head,i)
  End
Step 6 -> In Main()
  Create list using node* head = NULL
  Insert elements through push(&head, 89)
  Call reverse(head)
STOP

ตัวอย่างโค้ด C

#include
#include
// โครงสร้างโหนด
struct node {
    int data;
    struct node* next;
}
void push(struct node** headref, int newdata) {
    struct node* newnode = (struct node*) malloc(sizeof(struct node));
    newnode->data = newdata;
    newnode->next = (*headref);
    (*headref) = newnode;
}
int get(struct node* head) {
    int count = 0;
    struct node* newme = head;
    while (newme != NULL){
        count++;
        newme = newme->next;
    }
    return count;
}
int getN(struct node* head, int n) {
    struct node* cur = head;
    for (int i=0; inext;
    return cur->data;
}
void reverse(node *head) {
    int n = get(head);
    for (int i=n; i>=1; i--)
        printf("%d ", getN(head, i));
}
int main() {
    struct node* head = NULL; // สร้างโหนดแรก
    push(&head, 89); // เพิ่มองค์ประกอบในลิสต์
    push(&head, 42);
    push(&head, 33);
    push(&head, 21);
    push(&head, 10);
    reverse(head); // เรียกฟังก์ชัน reverse
    return 0;
}

ผลลัพธ์

การรันโปรแกรมจะได้ผลลัพธ์ดังนี้:

89 42 33 21 10