크래프톤 정글 - TIL

크래프톤 정글 5기 TIL - Day 24(C언어 자료구조 - 연결 리스트)

개발찾아 삼만리 2024. 4. 12. 23:45

1. 정렬하면서 노드 삽입하기

  • ll->head가 없는경우
  • 가장 작은 수가 들어오는 경우
  • 중간 크기의 수가 들어오는 경우
  • 가장 큰 수가 들어오는 경우
int insertSortedLL(LinkedList *ll, int item)
{
    ListNode *pre, *cur, *temp;

    if (ll->head == NULL)
    {
        cur = ll->head;
        ll->head = malloc(sizeof(ListNode));
        ll->head->item = item;
        ll->head->next = NULL;
        ll->size++;
        printf("Head 추가\n");
        return 0;
    }

    cur = ll->head;
    pre = NULL;

    while (cur != NULL)
    {
        if (cur->item == item)
        {
            return -1;
        }
        if (cur->item < item)
        {
            pre = cur;
            cur = cur->next;
        }
        else
        {
            temp = malloc(sizeof(ListNode));
            temp->item = item;
            if (pre == NULL) // 만약 맨 앞에 추가하는 경우
            {
                temp->next = ll->head;
                ll->head = temp;
            }
            else
            {
                temp->next = cur;
                pre->next = temp;
            }
            ll->size++;
            return 0;
        }
    }

    // 리스트의 끝까지 도달했을 때
    temp = malloc(sizeof(ListNode));
    temp->item = item;
    temp->next = NULL;

    pre->next = temp; // 이전 노드와 새로운 노드를 연결

    ll->size++;
    return 0;
}

2. 차례대로 노드 합치기

  • 한 칸씩 이동하는 것이 아닌 두 칸씩 이동
  • 2번 리스트에 남는 것이 있을 수 있기 떄문에 ll2->head로 추적
void alternateMergeLinkedList(LinkedList *ll1, LinkedList *ll2)
{
	ListNode *cur1, *cur2, *temp;
	cur1 = ll1->head;
	cur2 = ll2->head;

	while (cur1 != NULL && cur2 != NULL)
	{
		ll2->head = cur2->next;
		temp = cur2->next; // cur2의 다음 노드를 저장해둠
		cur2->next = cur1->next;
		cur1->next = cur2;
		cur1 = cur2->next; // cur1을 다음 위치로 이동
		cur2 = temp;	   // cur2를 다음 위치로 이동
	}
}

3. 홀수를 가진 노드를 뒤로 넣어 정렬하기

  • tail을 지정해서 홀수가 나오면 tail에 연결하는 방식으로 풀어봤는데 실패..

실패 코드

// 실패 코드
void moveOddItemsToBack(LinkedList *ll)
{
	ListNode *cur, *prev, *tail, *temp;
	cur = ll->head;
	int size = ll->size;
	while (cur != NULL)
	{
		prev = cur;
		cur = cur->next;
		tail = prev;
	}

	cur = ll->head;

	for (int i = 0; i < size; i++)
	{
		if (cur->item % 2 == 0)
		{
			prev = cur;
		}
		else
		{
			temp = cur;
			tail->next = temp;
			tail = temp;
			tail->next = NULL;
			prev->next = cur->next;
		}
		cur = cur->next;
	}
}