WEEK 05 C언어 링크드 리스트 1번 문제(4월13일 일요일)

C언어 링크드 리스트 1번 문제

[문제내용]

1. insertSortedLL

사용자로부터 정수를 입력받아 오름차순 정렬된 연결 리스트에 삽입하는 C 함수 작성.

※ 이미 존재하는 값은 삽입하지 않음

※ 삽입 성공 시 인덱스를 반환, 실패 시 -1 반환

함수 원형:

int insertSortedLL(LinkedList *ll, int item);

예시:

• 기존 리스트: 2, 3, 5, 7, 9 → 입력: 8 → 결과 리스트: 2, 3, 5, 7, 8, 9 → 반환값: 4
  
• 기존 리스트: 5, 7, 9, 11, 15 → 입력: 7 (중복됨) → 삽입되지 않음, 반환값: -1
  

[풀이 방법]

이 문제를 풀기 위해서는 3가지 조건을 고려해야한다.

1. 리스트 자체가 없으면(NULL)이면 -1리턴
2. 리스트가 NULL로 비었으면 노드 추가
3. 리스트에 이미 값이 있다면, 현재 기준에 따라 크냐 작냐에 따라 처리

[코드와 해설]

int insertSortedLL(LinkedList *ll, int item)   // LinkedList *ll: 연결리스트 구조체 가르킴, int item:리스트에 넣고 싶은 값
{
	/* 
	1. 리스트 자체가 없으면 -1 리턴
	2. 리스트가 NULL로 비었으면 노드 추가
	3. 리스트에 이미 값이 있으면, 현재 기준에 따라 크냐 작냐에 따라 처리
	*/

	ListNode *temp;   // 현재 노드를 가르키는 포인터
	int curindex = 0;    // 현재 몇 번 노드를 보고 있는지 추적하는 변수(최종적으로 삽입할 인덱스)

	// 리스트 자체가 없으면 -1
	if(ll == NULL){   // 연결리스트 자체가 NULL이면 실패 반환
		return -1;
	}
	else{ // 리스트안에 처리
		// 리스트 내용이 NULL이면 수행
		temp = ll -> head;   // 연결리스트의 첫 번째 노드부터 시작
		while(curindex <= ll -> size){  // 리스트 끝까지 탐색
			if(curindex == ll -> size){  // 연결 리스트에 아무것도 없음(현재 인덱스랑 전체 사이즈랑 같다)
				insertNode(ll, curindex, item);   //노드 추가
				break;
			}

			// 리스트에 이미 값이 있다면 기준보다 크냐 작냐에 따라 처리
			// 오름차순 정렬에 따라 값 인서트
			else{
				if(temp->item > item){  // 현재 노드 값이 새 값보다 클 경우
					insertNode(ll, curindex, item);  //바로 그 위치에 삽입
					break;
				}
				else if(temp->item < item){  // 만약, 현재 노드 값이 새 값보다 작다면
					curindex = curindex + 1;  // 다음 노드로 이동하기 위해 인덱스 +1
					temp =temp->next;  // 노드 위치도 이동시킨다

				}
				else{  // 이미 존재할 경우 예외처리
				return -1;  // 리턴 -1 반환
				break;
				}
			}
		}
	}
	return curindex;  // 현재 리스트 값들 출력
}

단계별로 기능을 할수 있게 만들었다. 블로그글들을 참고하여 만들었다.