문제 : boj 1158 (연결리스트 연습 문제)
풀이
- 연결리스트를 구현하여 풀이(먼저 node를 더하고 지우는 함수를 구현)
- 입력된 N만큼 연결리스트의 노드를 연결
- 시작점 1에서 부터 K번째에 있는 노드의 값을 출력하고 노드를 제거, K+1번째 노드가 1이되고 그 노드를 기준으로 K번째 노드를 반복해서 출력 및 제거
#include <iostream>
using namespace std;
struct node{
int data;
node* link;
};
void delete_node(node *head);
void add_node(node *head, int data){
node *new_node = new node;
new_node->data = data;
new_node->link = head->link;
head->link = new_node;
}
node* find_Kth(int K, node *curr){
int tmp;
for(int k(0);k < K-2; k++){
curr = curr->link;
}
return curr;
}
int main(){
freopen("input.txt", "r", stdin);
int N, K;
node *n1 = new node;
n1->link=nullptr;
cin >> N >> K;
node *curr =n1;
n1->data = 1;
for(int n(2); n < N+1; n++){
add_node(curr, n);
curr = curr->link;
}
curr->data=N;
curr->link=n1;
curr=n1;
if(K == 1){
cout << "<";
while(curr->link !=n1){
cout << curr->data << ", ";
curr = curr->link;
}
cout << curr->data << ">";
}
else{
cout << "<";
while(curr != curr->link){
curr = find_Kth(K, curr);
cout << curr->link->data << ", ";
delete_node(curr);
curr = curr->link;
}
cout << curr->data << ">";
}
fclose(stdin);
return 0;
}
void delete_node(node *head){
node* target = head->link;
head->link=target->link;
delete target;
}