오름차순으로 배열된 연결된 목록이 주어지면 목록을 한 번만 순회하여 중복 노드를 제거하는 함수를 작성하십시오. 예를 들어, 목록 이 문제를 연습 목록이 정렬되어 있으므로 목록을 아래로 진행하여 인접한 노드를 비교할 수 있습니다. 인접한 노드가 같으면 두 번째 노드를 제거합니다. 삭제하기 전에 다음 노드 이후의 노드를 기록해야 하는 까다로운 경우가 있습니다. 알고리즘은 C, Java 및 Python에서 다음과 같이 구현할
수 있습니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 #include <stdio.h> #include <stdlib.h> // 연결된 목록 노드 structNode { int
data; structNode*next; };
// 주어진 연결된 목록를 출력하는 도우미 함수 voidprintList(structNode*head) { structNode*ptr=
head; while(ptr) { printf("%d —> ",ptr->data); ptr=ptr->next; } printf("NULL"); } // 연결된 목록의 시작 부분에 새 노드를 삽입하는 도우미 함수 void
push(structNode**head,int
data) { structNode*newNode
=(struct
Node*)malloc(sizeof(struct
Node)); newNode->data=
data; newNode->next=*head;
*head=newNode; } // 정렬된 목록에서 중복 제거 void
removeDuplicates(structNode*head) { // 리스트가 비어있으면 아무것도
하지 않는다 if(head==NULL){ return; } struct
Node*current=head; // 현재 노드와 다음 노드를 비교 while(current->next!=NULL) { if(current->data==
current->next->data) { structNode*nextNext=current->next->next; free(current->next); current->next=nextNext; } else{ current=
current->next; // 삭제가 없을 때만 진행 } } } intmain(void) { // 입력 키 intkeys[]={1,
2,2,2,3,
4,4,5}; int
n=
sizeof(keys)/sizeof(keys[0]);
// 연결된 목록의 헤드 노드를 가리킨다. structNode*head
=NULL; // 연결된 목록 생성 for(int
i=n-1;i>=
0;i--){ push(&head,keys[i]); } removeDuplicates(head); // 연결된 목록 출력 printList(head); return0; } 다운로드 코드 실행 결과: Java
다운로드 코드 실행 결과: Python
다운로드 코드 실행 결과: 위 솔루션의 시간 복잡도는 O(n), 어디 읽어 주셔서 감사합니다. 우리의 온라인 컴파일러 C, C++, Java, Python, JavaScript, C#, PHP 및 기타 널리 사용되는 프로그래밍 언어를 사용하여 주석에 코드를 게시합니다. 우리처럼? 우리를 친구에게 소개하고 우리가 성장할 수 있도록 도와주세요. 행복한 코딩 :) |