> 백엔드 개발 > C++ > 본문

C++를 사용하여 연결 목록의 마지막 노드 삭제

王林
풀어 주다: 2023-08-30 19:09:03
앞으로
1211명이 탐색했습니다.

C++를 사용하여 연결 목록의 마지막 노드 삭제

단일 연결된 목록이 있고 우리의 작업은 이 연결된 목록에서 마지막 노드를 삭제하는 것입니다. 이 문제에서는 주어진 연결 리스트를 순회하고 마지막 노드만 삭제하면 됩니다.

해결 방법을 찾는 방법

이 방법에서는 주어진 연결 목록을 탐색하고 이전 노드와 현재 노드를 추적합니다. 현재 노드가 마지막 노드가 되면 이전 -> 다음을 NULL로 변경하고 현재 노드를 삭제합니다.

Example

#include <iostream>
using namespace std;

struct Node {
   int data;
   struct Node* next;
};
void push(struct Node** ref, int new_data) { // pushing the node
   struct Node* new_n = new Node;
   new_n->data = new_data;
   new_n->next = (*ref);
   (*ref) = new_n;
}
int main() {
   Node* head = NULL;
   push(&head, 12);
   push(&head, 29);
   push(&head, 11);
   push(&head, 23);
   push(&head, 8);
   auto curr = head, prev = head;
   if (!curr || !curr -> next) // if list only has one element or the list is empty
      cout << "Empty\n";
   else {
      while (curr) { // while curr != NULL
         if (!curr -> next) {
            prev -> next = NULL;
            delete(curr); // freeing the space
            break;
         }
         prev = curr;
         curr = curr -> next; // moving to the next node
      }
   }
   for (Node* temp = head; temp != NULL; temp = temp->next) // printing the data
      cout << temp->data << " ";

   return 0;
}
로그인 후 복사

Output

8 23 11 29
로그인 후 복사

위 코드 설명

이 방법에서는 현재 노드와 이전 노드를 추적하면서 배열을 반복합니다. 현재 노드가 마지막 노드가 되면 이전 -> 옆을 NULL로 변경하고 현재 노드를 삭제합니다. 주어진 프로그램의 전체 시간 복잡도는 O(N)입니다. 여기서 N은 주어진 목록의 크기입니다.

시간 복잡도 - O(N)

N: 주어진 배열의 크기

결론

이 기사에서는 주어진 연결 목록에서 마지막 노드를 제거하는 문제를 해결했습니다. 우리는 또한 이 문제에 대한 C++ 프로그램과 이를 해결하기 위한 완전한 접근 방식을 배웠습니다. C, Java, Python 및 기타 언어와 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다. 이 기사가 도움이 되기를 바랍니다.

위 내용은 C++를 사용하여 연결 목록의 마지막 노드 삭제의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

원천:tutorialspoint.com
본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
인기 튜토리얼
더>
최신 다운로드
더>
웹 효과
웹사이트 소스 코드
웹사이트 자료
프론트엔드 템플릿
회사 소개 부인 성명 Sitemap
PHP 중국어 웹사이트:공공복지 온라인 PHP 교육,PHP 학습자의 빠른 성장을 도와주세요!