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 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