[C언어] Linked List (2) - alternateMergeLL 함수 구현하기

Linked List (2) - alternateMergeLL 함수 구현하기

두 번째 리스트의 노드들을 첫 번째 리스트의 자리 사이사이에 삽입하는 함수.

주어진 요소 확인하기

구조체

• LinkedList: (struct) 연결 리스트 구조체
  • size: (int field) 연결 리스트 요소 갯수
  • *head: (pointer field) 연결 리스트 첫 노드의 주소
• ListNode: (struct) 노드 구조체
  • item: (int field) 노드의 값
  • *next: (pointer field) 다음 노드의 주소

alternateMergeLL 함수의 매개 변수

• *ll1: (pointer) 첫번째 연결 리스트 주소
• *ll2: (pointer) 두번째 연결 리스트 주소

 

핵심 아이디어

• ll1의 사이사이에 삽입하기 때문에 ll1->size - 1개 삽입 가능, 곧 ll1->size <= 1이면 return
• 카운터(i)가 ll1->size - 1에 도달하거나, ll2->head가 NULL이 될 때까지 삽입을 반복
  • 먼저, ll2의 첫 노드(ll2->head)을 떼오고(cur2), ll2->head를 cur2->next로 설정
  • ll1에 현재 삽입할 인덱스의 노드(cur1)를 이용해 떼온 노드 cur2를 삽입
  • 삽입 후 현재 삽입할 인덱스 노드를 두 칸 뒤로 이동(한 칸 뒤는 새로 삽입한 cur2이므로)
  • ll1->size 1 증가 및 ll2->size 1 감소

 

구현하기

void alternateMergeLinkedList(LinkedList *ll1, LinkedList *ll2)
{
    if (ll1 == NULL || ll2 == NULL) return;
    if (ll1->size <= 1 || ll2->size == 0) return;

	ListNode *cur1 = ll1->head;
	ListNode *cur2;
	int i = 0;
	while (i < ll1->size - 1 && ll2->head != NULL) {
		cur2 = ll2->head;
		ll2->head = cur2->next;
	
		cur2->next = cur1->next;
		cur1->next = cur2;
		
		cur1 = cur1->next->next;

		ll1->size++;
		ll2->size--;
		i++;
	}
}