오름차순으로 배열된 연결된 목록이 주어지면 목록을 한 번만 순회하여 중복 노드를 제거하는 함수를 작성하십시오. 예를 들어, 목록 {1, 2, 2, 2, 3, 4, 4, 5} 목록으로 변환해야 합니다 {1, 2, 3, 4, 5}. 이 문제를 연습 목록이 정렬되어 있으므로 목록을 아래로 진행하여 인접한 노드를 비교할 수 있습니다. 인접한 노드가 같으면 두 번째 노드를 제거합니다. 삭제하기 전에 다음 노드 이후의 노드를 기록해야 하는 까다로운 경우가 있습니다. 알고리즘은 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; }C
다운로드 코드 실행
결과:
1 —> 2 —> 3 —> 4 —> 5 —> NULL
Java
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 | // 연결된 목록 노드 classNode { intdata; Node next; Node(intdata,Node next) { this.data= data; this.next=next; } } classMain { // 주어진 연결된 목록를 출력하는 도우미 함수 publicstaticvoidprintList(Node head) { Node ptr=head; while(ptr!=null) { System.out.print(ptr.data +" —> "); ptr= ptr.next; } System.out.println("null"); } // 정렬된 목록에서 중복 제거 publicstaticNode removeDuplicates(Node head) { // 리스트가 비어있으면 아무것도 하지 않는다 if(head ==null){ returnnull; } Node current=head; // 현재 노드와 다음 노드를 비교 while(current.next !=null) { if (current.data== current.next.data) { Node nextNext=current.next.next; current.next=nextNext; } else{ current= current.next; // 삭제가 없을 때만 진행 } } returnhead; } publicstaticvoidmain(String[] args) { // 입력 키 int[]keys={1, 2,2,2,3, 4,4,5}; // 연결된 목록의 헤드 노드를 가리킨다. Node head=null; // 연결된 목록 생성 for(inti= keys.length-1;i>= 0;i--){ head=newNode(keys[i], head); } head= removeDuplicates(head); // 연결된 목록 출력 printList(head); } } |
다운로드 코드 실행
결과:
1 —> 2 —> 3 —> 4 —> 5 —> null
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 | # 연결된 목록 노드 classNode: def __init__(self,data=None, next=None): self.data =data self.next=next # 주어진 연결된 목록를 출력하는 도우미 기능 defprintList(head): ptr =head whileptr: print(ptr.data,end=' —> ') ptr=ptr.next print('None') # 정렬된 목록에서 중복 제거 defremoveDuplicates(head): # 목록이 비어 있으면 아무 작업도 수행하지 않습니다. ifhead isNone: returnNone current=head # 현재 노드를 다음 노드와 비교 while current.next: ifcurrent.data ==current.next.data: nextNext=current.next.next current.next=nextNext else: current=current.next #는 삭제가 없는 경우에만 진행 returnhead if__name__=='__main__': # 입력 키 keys=[1,2, 2,2,3,4, 4,5] # 연결된 목록을 구성합니다. head= None foriin reversed(range(len(keys))): head=Node(keys[i], head) head=removeDuplicates(head) # 연결된 목록 인쇄 printList(head) |
다운로드 코드 실행
결과:
1 —> 2 —> 3 —> 4 —> 5 —> None
위 솔루션의 시간 복잡도는 O(n), 어디 n 연결된 목록의 총 노드 수이며 추가 공간이 필요하지 않습니다.
원천: //cslibrary.stanford.edu/105/LinkedListProblems.pdf
읽어 주셔서 감사합니다.
우리의 온라인 컴파일러 C, C++, Java, Python, JavaScript, C#, PHP 및 기타 널리 사용되는 프로그래밍 언어를 사용하여 주석에 코드를 게시합니다.
우리처럼? 우리를 친구에게 소개하고 우리가 성장할 수 있도록 도와주세요. 행복한 코딩 :)