크래프톤 정글 week05, day35 - 연휴 과제 - 연결리스트

1번 문제 - 삽입정렬 연결리스트 함수

int insertSortedLL(LinkedList *ll, int item)
{
	/* add your code here */
	// 현재 노드와 새 노드를 선언하고 index를 0으로 초기화
	ListNode *cur;
	ListNode *newNode;
	int index = 0;

	// 현재 노드에 리스트의 첫 노드값을 넣고
	cur = ll->head;
	// 현재 노드가 값이 있는 동안
	while(cur != NULL) {
		// 만약 현재 노드의 값이 입력된 값과 같으면 -1을 반환
		if(cur->item == item){
			return -1;
		}
		cur = cur->next;
	}

	// 현재 노드를 리스트의 첫 노드로 넣기
	cur = ll->head;

	// 연결리스트의 첫 노드가 NULL이거나 첫 노드의 값이 삽입하는 값보다 크면
	if(ll->head == NULL || ll->head->item > item) {
		// 노드삽입 함수를 실행하고 인덱스 값을 반환
		insertNode(ll, 0, item);
		return index;
	}

	// 현재 노드의 다음 노드가 NULl이 아니고 현재 노드의 다음 노드 값이 삽입 값보다 작을 동안 반복
	while(cur->next != NULL && cur->next->item < item){
		// 현재 노드에 다음 노드값을 넣고 index를 1올린다.
		cur = cur->next;
		index++;
	}

	// ListNode의 크기만큼 동적할당하고 값에 삽입 값을 넣기기
	newNode = malloc(sizeof(ListNode));
	newNode->item = item;
	// 새 노드의 다음 노드에 현재 노드의 다음 노드로 넣고
	newNode->next = cur->next;
	// 현재 노드의 다음 노드에 새 노드를 넣기
	cur->next = newNode;
	// 리스트의 크기를 1 올린다.
	ll->size++;

	// 삽입 노드의 인덱스 값을 반환(노드 위치를 알기 위해 +1)
	return index + 1;
}

 

 

2번 문제 - 순서대로병합하는 함수

void alternateMergeLinkedList(LinkedList *ll1, LinkedList *ll2)
{
	// 현재 노드1과 2에 리스트1과 2의 첫 노드를 넣기
	ListNode *cur1 = ll1->head;
	ListNode *cur2 = ll2->head;
	// 노드1과 노드2의 다음 노드를 넣을 변수들 선언
	ListNode *next1, *next2;
	// 이전 노드를 기억할 변수 선언 후 초기화
	ListNode *prev = NULL;

	// 현재노드 1과 2가 존재하는 동안 반복
	while(cur1 != NULL && cur2 != NULL) {
		// 현재 노드의 다음 노드를 next변수에 넣기
		next1 = cur1->next;
		next2 = cur2->next;

		// 만약 이전 노드가 존재한다면
		if(prev != NULL)
			// 이전 노드의 다음 노드에 현재 노드1을 넣기
			prev->next = cur1;
		// 존재하지 않는다면
		else
			// 리스트1의 첫 노드에 현재 노드1을 넣기
			ll1->head = cur1;

		// 현재노드1의 다음 노드에 현재노드2를 넣기
		cur1->next = cur2;
		// 이전 노드에 현재노드2를 넣고 다음 노드들을 현재노드에 넣기
		prev = cur2;
		cur1 = next1;
		cur2 = next2;
	}

	// 병합 과정이 끝난 후 병합노드의 다음 노드를 설정
	// 만약 이전 노드가 존재하면서
	if(prev != NULL) {
		// 현재노드1이 존재한다면
		if(cur1 != NULL)
			// 이전 노드의 다음 노드에 현재노드1을 넣기
			prev->next = cur1;
		// 존재하지 않는다면
		else
			// 이전 노드의 다음 노드에 NULL값 넣기
			prev->next = NULL;
	}

	// 리스트1의 노드수를 0으로 만들고 현재노드1을 리스트1의 첫 노드에 넣기
	ll1->size = 0;
	cur1 = ll1->head;
	// 현재노드1이 존재하는 동안 반복
	while(cur1 != NULL) {
		// 리스트1의 노드수를 1씩 증가하며 현재노드1에 다음노드를 넣기
		ll1->size++;
		cur1 = cur1->next;
	}


	// 리스트2의 첫 노드를 현재노드2로 넣고 리스트2의 노드 수를 0으로 만들기
	ll2->head = cur2;
	ll2->size = 0;
	// 현재노드2에 리스트2의 첫 노드를 넣기
	cur2 = ll2->head;
	// 현재노드2가 존재하는 동안 반복
	while(cur2 != NULL) {
		// 리스트2의 노드수를 1씩 증가하며 현재노드2에 다음노드를 넣기
		ll2->size++;
		cur2 = cur2->next;
	}

}

 

 

3번 문제 - 홀수노드를 뒤로 보내는 함수

void moveOddItemsToBack(LinkedList *ll){
	// 리스트를 순회하는 노드를 가리키는 temp 변수
    ListNode *temp;
	// temp에 리스트의 첫 노드값을 넣기
    temp = ll->head;
	// 홀수노드개수 oddcount, 반복문 제어 i, 
	// 홀수인덱스저장 oddindex, 홀수노드값 odditem
    int oddcount = 0;
    int i;
    int oddindex = 0;
    int odditem;

	// 노드가 존재하는 동안 반복
    while(temp != NULL){
		// 만약 노드가 양수와 음수 둘다 홀수일 경우 홀수개수를 1증가
        if(temp->item % 2 == 1 || temp->item % 2 == -1){
            oddcount ++;
        }
		// temp에 다음 노드를 넣기
        temp = temp->next;
    }

	// 홀수 개수만큼 반복하며 temp와 홀수인덱스를 초기화
    for(i = 0; i < oddcount; i++){
        temp = ll->head;
        oddindex = 0;
		// 노드가 존재하는 동안 반복
        while(temp != NULL){
			// 만약 노드값이 홀수일 때 while문을 빠져나가기
            if(temp->item %2 == 1 || temp->item %2 == -1){
                break;
            }
			// while문이 도는 동안 홀수인덱스를 1씩 증가하고 temp에 다음 노드를 넣기
            oddindex++;
            temp = temp->next;
        }
		// 만약 노드가 존재한다면
        if(temp != NULL){
			// 홀수값에 노드의 값을 넣고 
            odditem = temp->item;
			// 노드 제거 함수를 사용해 홀수를 제거 후
            removeNode(ll, oddindex);
			// 다시 삽입 함수를 이용하여 맨 뒤에 홀수를 넣기
            insertNode(ll, ll->size, odditem);
        }
    }
}

​

 

 

4번 문제 - 짝수노드를 뒤로 보내는 함수

void moveEvenItemsToBack(LinkedList *ll)
{
	// 리스트를 순회하는 노드를 가리키는 temp 변수
    ListNode *temp;
	// temp에 리스트의 첫 노드값을 넣기
    temp = ll->head;
	// 짝수노드개수 evencount, 반복문 제어 i, 
	// 짝수인덱스저장 evenindex, 짝수노드값 evenitem
    int evencount = 0;
    int i;
    int evenindex = 0;
    int evenitem;

	// 노드가 존재하는 동안 반복
    while(temp != NULL){
		// 만약 노드가 양수와 음수 둘다 짝수일 경우 짝수개수를 1증가
        if(temp->item % 2 == 0){
            evencount ++;
        }
		// temp에 다음 노드를 넣기
        temp = temp->next;
    }

	// 짝수 개수만큼 반복하며 temp와 짝수인덱스를 초기화
    for(i = 0; i < evencount; i++){
        temp = ll->head;
        evenindex = 0;
		// 노드가 존재하는 동안 반복
        while(temp != NULL){
			// 만약 노드값이 짝수일 때 while문을 빠져나가기
            if(temp->item %2 == 0){
                break;
            }
			// while문이 도는 동안 짝수인덱스를 1씩 증가하고 temp에 다음 노드를 넣기
            evenindex++;
            temp = temp->next;
        }
		// 만약 노드가 존재한다면
        if(temp != NULL){
			// 짝수값에 노드의 값을 넣고 
            evenitem = temp->item;
			// 노드 제거 함수를 사용해 짝수를 제거 후
            removeNode(ll, evenindex);
			// 다시 삽입 함수를 이용하여 맨 뒤에 짝수를 넣기
            insertNode(ll, ll->size, evenitem);
        }
    }
}

 

 

5번 문제 - 연결리스트 반절 쪼개는 함수

• 이 문제는 특이하게 플로이드 워셜 알고리즘 중에 토끼와 거북이라는 알고리즘을 이용했다.

void frontBackSplitLinkedList(LinkedList *ll, LinkedList *resultFrontList, LinkedList *resultBackList)
{
	// 토끼와 거북이 알고리즘 사용
	// 거북이 slow, 토끼 fast, 이전 노드를 기억하는 prev를 초기화, 인덱스 index
	ListNode *slow = ll->head;
	ListNode *fast = ll->head;
	ListNode *prev = NULL;
	int index = 0;

	// 토끼와 토끼의 다음노드가 존재한다면
	while(fast != NULL && fast->next != NULL){
		// 이전 노드에 거북이를 넣기
		prev = slow;
		// 거북이에는 거북이의 다음노드를 넣고
		slow = slow->next;
		// 토끼에는 토끼의 다음다음 노드를 넣고 인덱스를 1증가
		// 기본적으로 거북이는 1칸 토끼는 2칸을 이동하기 때문
		fast = fast->next->next;
		index++;
	}

	// 만약 리스트의 노드개수가 홀수라면
	if(ll->size % 2 == 1) {
		// 이전 노드에 거북이를 넣고
		// 홀수일 경우 앞리스트에 하나 더 넣기 위함
		prev = slow;
		// 거북이에는 거북이의 다음노드를 넣고 인덱스를 1증가
		slow = slow->next;
		index++;
	}

	// 만약 이전 노드가 존재하면
	if(prev != NULL)
		// 이전노드의 다음노드 즉, 현재 노드를 초기화
		prev->next = NULL;

	// 앞리스트의 첫 노드를 리스트의 첫 노드로 넣기
	resultFrontList->head = ll->head;
	// 앞리스트의 노드개수에 index값을 넣기
	resultFrontList->size = index;

	// 뒷리스트의 첫 노드를 거북이로 넣기
	resultBackList->head = slow;
	// 뒷리스트의 노드개수를 리스트의 노드개수-인덱스값으로 넣기
	resultBackList->size = ll->size - index;
}

 

 

6번 문제 - 최대값을 맨 앞으로 가지고 오는 함수

// 매개변수 **ptrHead는 리스트의 처음 노드의 위치를 저장하기위함
int moveMaxToFront(ListNode **ptrHead)
{
	// 만약 처음 노드가 존재하거나 처음 노드의 다음이 NULL일 때 0 반환
    if(*ptrHead == NULL || (*ptrHead)->next == NULL)
		return 0;

	// 최대값을 가진 노드의 이전 노드
	ListNode *maxPrevNode = NULL;
	// 현재까지 찾은 최대값을 가진 노드
	ListNode *maxNode = *ptrHead;
	// 순회중인 노드의 이전노드. 현재 노드가 최대값일 때 이전노드를 maxprevNode로 설정하기 위함
	ListNode *prevNode = NULL;
	// 현재 노드에 처음 노드를 넣기
	ListNode *curNode = *ptrHead;

	// 현재 노드가 존재하는 동안 반복
	while(curNode != NULL) {
		// 만약 현재노드의 값이 최대값보다 크다면
		if(curNode->item > maxNode->item) {
			// 최대값에 현재노드를 넣고 최대값 이전노드에 이전노드를 넣기
			maxNode = curNode;
			maxPrevNode = prevNode;
		}
		// 이전노드에 현재노드를 넣고 현재노드에 다음 노드를 넣기
		prevNode = curNode;
		curNode = curNode->next;

		// 만약 최대값 노드가 리스트의 처음노드가 아닐 때
		if(maxPrevNode != NULL) {
			// 최대값이전노드의 다음위치를 최대값의 다음으로 함으로써 최대값을 넘기기
			maxPrevNode->next = maxNode->next;
			// 최대값의 다음 노드는 처음 노드를 넣기
			maxNode->next = *ptrHead;
			// 처음 노드에 최대값을 넣기
			*ptrHead = maxNode;
		}

		return 1;
	}
}

 

 

7번 문제 - 재귀방식의 리버스 함수

void RecursiveReverse(ListNode **ptrHead)
{
	// 만약 첫 노드가 없거나 첫 노드의 다음노드가 없으면 반환
	if(*ptrHead == NULL || (*ptrHead)->next == NULL)
		return;

	// 첫 노드를 제외한 노드 관리 rest 에 첫 노드의 다음 노드를 넣기
	ListNode *rest = (*ptrHead)->next;
	// rest의 주소값을 인자로 넣고 재귀 함수 시작
	RecursiveReverse(&rest);

	// 첫 노드의 다음 다음 노드를 첫 노드를 가리키도록 한다.
	(*ptrHead)->next->next = *ptrHead;
	// 첫 노드의 다음 노드에 NULL을 넣으면
	// 첫노드가 끝노드가 되어 다른 노드를 가리키지 않게 된다.
	(*ptrHead)->next = NULL;
	// 첫 노드를 뒤집힌 리스트의 새로운 노드로 갱신한다
	*ptrHead = rest;
}

 

연휴에 못풀었던 알고리즘 문제들과 책들을 정독하고 싶었는데 연휴 과제가 빡빡하게 들어오는 바람에 계속 이것만 보고 있다. 코치님 안 그래도 할게 많은데 살려주세요

​

 

학습 시간 : 13 ~ 25시