งานคือการพิมพ์โหนดที่เริ่มต้นจากจุดสิ้นสุดของรายการที่เชื่อมโยงโดยไม่ต้องใช้ช่องว่างเพิ่มเติม ซึ่งหมายความว่าไม่ควรมีตัวแปรเพิ่มเติมใด ๆ แทนตัวชี้ส่วนหัวที่ชี้ไปยังโหนดแรกจะถูกย้าย
ตัวอย่าง
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 and i<n-1 && cur != NULL and i++ Set cur=cur->next End Return cur->dataStep 5 -> Declare function void reverse(node *head) Declare int n = get(head) Loop For int i=n and i>=1 and 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
ตัวอย่าง
#include<stdio.h>
#include<stdlib.h>
//node structure
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; i<n-1 && cur != NULL; i++)
cur = cur->next;
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; //create a first node
push(&head, 89); //pushing element in the list
push(&head, 42);
push(&head, 33);
push(&head, 21);
push(&head, 10);
reverse(head); //calling reverse function
return 0;
} ผลลัพธ์
หากเรารันโปรแกรมด้านบน มันจะสร้างผลลัพธ์ดังต่อไปนี้
89 42 33 21 10
