[리스트ADT] 원형 리스트 문제

촛불이 N개 꽃혀있는 케이크에서 k번개씩 건너 뛰면서 촛불을 끌 때,

마지막으로 남아 있는 촛불을 어떻게 될까?

 

[ 배열로 구현 ]

int runSimulation(int* arr,int N, int n, int k) {
	int cur = 0;
	while (n > 1) {
		int cnt=1;
		while (cnt < k) {
			cur=(cur+1)%N;
			if (arr[cur] != 0) {
				cnt++;
			}
		}
		
		arr[cur] = 0;
		n--;
		while (arr[cur] == 0) {
			cur = (cur + 1) % N;
		}
	}
	return cur;
}

 

[ 원형 리스트 ]

int runSimulation(Node* list,int N, int n, int k) {
	Node* cur = list;
	while (n > 1) {
		int cnt = 0;
		while (cnt < k) {
			
			cur = cur->next;
			if (cur->data != 0) {
				cnt++;
			}
		}
		cur->data = 0;
		

		while (cur->data == 0) {
			cur = cur->next;
		}
		n--;
	}
	return cur->idx;
}

 

---

[ 원형 리스트 ADT 구현 시 주의점 ]

아래 코드가 틀린 이유는?

void buildList(Node* list, int n) {
	Node* prev = list;
	int idx = 1;
	int N = n;
	while (N > 1) {
		
		Node* newNode = (Node*)malloc(sizeof(Node));
		newNode->idx = idx++;
		newNode->prev = prev;
		newNode->next = list;
		newNode->data = 1;

		prev = newNode;
		N--;
	}
}

 

 

새로운 노드에 이전 주소를 입력을 해주었지만, 이전 노드의 다음 주소를 입력하지 않았다.

이전 노드의 next에 값을 넣지 않음

따라서, 아래 코드로 수정해야한다.

 

void buildList(Node* list, int n) {
	Node* prev = list;
	int idx = 1;
	int N = n;
	while (N > 1) {
		
		Node* newNode = (Node*)malloc(sizeof(Node));
		newNode->idx = idx++;
		newNode->prev = prev;
		newNode->next = list;
		newNode->data = 1;
        // 아래 코드 주의!!!
		prev->next = newNode;


		prev = newNode;
		N--;
	}
}