수다닷컴

#include stdio.h
#include stdlib.h
//단순 연결 리스트 구현
typedef int element;
typedef struct ListNode {
element data;
struct ListNode *link;
} ListNode;
//에러 호출 프로그램
void error(char *message)
{
fprintf(stderr,%s\n,message);
exit(1);
}
//단순 연결 리스트의 삽입 함수 C
void insert_node(ListNode **phead, ListNode *p,
ListNode *new_node)
{
if( *phead == NULL ){// 공백리스트인 경우
new_node-link = NULL;
*phead = new_node;
}
else if( p == NULL ){ // p가 NULL이면 첫번째 노드로 삽입
new_node-link = *phead;
*phead = new_node;
}
else { // p 다음에 삽입
new_node-link = p-link;
p-link = new_node;
}
}
// 노드를 동적으로 생성하는 프로그램
ListNode *create_node(element data, ListNode *link)
{
ListNode *new_node;
new_node = (ListNode *)malloc(sizeof(ListNode));
if( new_node == NULL ) error(메모리 할당 에러);
new_node-data = data;
new_node-link = link;
return(new_node);
}
//반복적인 리스트 방문 알고리즘
void display(ListNode *head)
{
ListNode *p=head;
while( p != NULL ){
printf(%d-, p-data);
p = p-link;
}
printf(\n);
}
//홀수 나누는 함수 split_A
void split_A(ListNode *head)
{
int *list_A = NULL;
//초기값 헤드부터
ListNode *pOddNode = head;
while(pOddNode != NULL)
{
//list_A에 데이터 저장
list_A = &pOddNode-data;
//값 출력
printf(list_A : %d\n, *list_A);
//2칸 건너 뛰어 이동
pOddNode = (pOddNode-link == NULL)?(NULL):(pOddNode-link-link);
}
printf(-------------------------------\n);
}
//짝수 나누는 함수 split_B
void split_B(ListNode *head)
{
int *list_B = NULL;
//초기값 헤드의 다음부터
ListNode *pEvenNode = (head-link == NULL)?(NULL):(head-link);
while(pEvenNode != NULL)
{
//list_B에 데이터 저장
list_B = &pEvenNode-data;
//값 출력
printf(list_B : %d\n, *list_B);
//2칸 건너 뛰어 이동
pEvenNode = (pEvenNode-link == NULL)?(NULL):(pEvenNode-link-link);
}
}
//테스트 프로그램
void main()
{
//단순 연결 리스트 삽입 함수 사용해서 list_C에 노드 삽입
ListNode *list_C = NULL;
insert_node(&list_C, NULL, create_node(10, NULL));
insert_node(&list_C, NULL, create_node(9, NULL));
insert_node(&list_C, NULL, create_node(8, NULL));
insert_node(&list_C, NULL, create_node(7, NULL));
insert_node(&list_C, NULL, create_node(6, NULL));
insert_node(&list_C, NULL, create_node(5, NULL));
insert_node(&list_C, NULL, create_node(4, NULL));
insert_node(&list_C, NULL, create_node(3, NULL));
insert_node(&list_C, NULL, create_node(2, NULL));
insert_node(&list_C, NULL, create_node(1, NULL));

//리스트 방문 알고리즘 사용해서 list_C 출력
display(list_C);

//list_C의 홀수번째 노드를 list_A에 이동시키는 함수 split_A 사용 list_A 출력
split_A(list_C);

//list_C의 짝수번째 노드를 list_B에 이동시키는 함수 split_B 사용 list_B 출력
split_B(list_C);
}단순연결 리스트 C를 두개의 단순 연결 리스트 A와 B로 분리하는 함수 split를 작성하여보자. C의 홀수번째 노드들은 모두 A로 이동되고, C의 짝수 번째 노드들은 모두 B로 이동된다. 이 함수가 C를 변경하여서는 안된다. 작성된 알고리즘의 시간 복잡도를 구하고, 구현하여 수행하여 보자.

위에 문제 푼건데 시간복잡도가 얼만지 잘 모르겠습니다.
시간복잡도가 얼만지 좀 알려주세요~
그리고 맞게 푼건지 확인좀 ㅎㅎ;

신청하기