[ 자료구조 ] Alternate Merge Linked List

김쟇연·2025년 4월 14일
Calternateinsertc언어linkedlistlistmerge교차삽입리스트병합메모리구조연결리스트자료구조포인터연습함수구현

Data Structures

목록 보기
2/6
post-thumbnail

그럼 이번에도 우리 함께~ ☺️

2번 문제 alternateMergeLL, 아주 쉽게 해석해볼게요!

우리 금쪽이들처럼 리스트 친구들을 다루는 거예요~

💛 “서로 사이좋게 끼워넣는 연습, 너무 귀여운 작업이죠~?”

Q2_A_LL (alternateMergeLL)

2. (alternateMergeLL) Write a C function alternateMergeLL() which inserts nodes of 
the  second  list  into  alternate  positions  of  the  first  list.  The  nodes  of  the  second  list  should 
only be inserted when there are alternate positions available in the first list. 
 
The function prototype is given as follows: void alternateMergeLL(LinkedList *ll1, LinkedList *ll2); 
 
For  an  example,  assume  that  given  two  linked  lists  are  LinkedList1  and  LinkedList2: 
LinkedList1: 1,  2,  3 
LinkedList2: 4,  5,  6,  7 
 
The resulting linked lists are:  
LinkedList1: 1,  4,  2,  5,  3,  6 
LinkedList2: 7 
 
The second list should become empty when the first list is larger than the second list. For an 
example, assume that given two linked lists are LinkedList1 and LinkedList2: 
LinkedList1: 1,  5,  7,  3,  9,  11 
LinkedList2: 6,  10,  2,  4 
 
The resulting Linked Lists are:  
LinkedList1: 1,  6,  5,  10,  7,  2,  3,  4,  9,  11  
LinkedList2: empty 
 
A sample input and output session is given below (if the current linked lists are Linked list 
1: 1,  2, 3 and Linked list 2: 4 , 5,  6,  7): 
 
Linked list 1: 1 2 3 
Linked list 2: 4 5 6 7 
 
Please input your choice(1/2/3/0): 3 
The resulting linked lists after merging the given linked list are: 
Linked list 1: 1 4 2 5 3 6 
Linked list 2: 7

📌 문제 요약 (쉽게 말하면?)

두 개의 줄(리스트)이 있어요.

첫 번째 줄에 두 번째 줄 친구들을 한 칸씩 교대로 끼워넣는 거예요!

근데 중요한 건!

👉 첫 번째 줄에 자리가 있을 때만 끼워요.

👉 첫 줄의 순서를 절대 망치면 안 돼요.

“들어갈 수 있는 자리가 있을 때만! 조심조심~” 😊

👧 비유로 말하자면…

리스트1은 큰 줄이고, 리스트2는 작은 줄이에요.

리스트2에 있는 친구들이 “나도 같이 줄 서고 싶어요~” 라고 했을 때,

리스트1의 아이들 사이에 교대로 들어가는 거예요.

예를 들어서요~

makefile

리스트1: A B C
리스트2: X Y Z W

리스트1 아이들 사이에

이렇게 끼워 넣는 거예요!

👉 A X B Y C Z

그리고 W는 아직 자리가 없어서 남겨두는 거예요.

“너는 다음 차례에 넣어줄게~” 😌

🔍 실제 예시 해석

✅ 예시 1

plaintext

리스트1: 1 2 3
리스트2: 4 5 6 7

➡️ 교대로 넣으면:

plaintext

리스트1: 1 4 2 5 3 6
리스트2: 7 (아직 자리 없음~ 기다려~)

✅ 예시 2

plaintext

리스트1: 1 5 7 3 9 11
리스트2: 6 10 2 4

➡️ 교대로 넣으면:

plaintext

리스트1: 1 6 5 10 7 2 3 4 9 11
리스트2: (없음! 다 넣었어요~)

💡 주의할 점!

상황처리 방법
리스트2가 더 짧다있는 것만 끼워넣고 끝!
리스트1이 더 짧다리스트1 사이사이 넣고, 남은 건 리스트2에 남겨둬요
리스트1이 비어 있다아무 데도 못 들어가요 😢

🎀 왜 이런 문제를 내는 걸까요?

이 문제는요~

단순히 연결을 바꾸는 문제가 아니에요.

리스트1의 구조를 존중하면서,

리스트2의 친구들을 틈틈이 정중하게 “끼워 넣는” 연습이에요.

함부로 순서를 바꾸거나,

다 넣으려고 억지로 끼워 넣으면 안 돼요~ ❌

💛 선생님의 말씀

“이 문제는요~

협동과 양보, 그리고 질서를 배우는 문제예요.

내가 먼저였다고 해서 끝까지 내 자리만 고수하는 게 아니라,

사이사이에 친구를 받아들이는 마음,

그게 바로 연결 리스트의 배려랍니다~

정말 잘하고 있어요~

너무 예뻐요~ 우리 금쪽이 한 번 더 안아주세요~ 🤗💛”

✏️ 요약

핵심 포인트설명
리스트2 → 리스트1교대로 한 칸씩 끼워 넣기
순서반드시 유지!
리스트2 남은 노드자리가 없으면 그냥 남겨둬요
리턴값없음. 두 리스트를 직접 수정

code

//////////////////////////////////////////////////////////////////////////////////

/* CE1007/CZ1007 Data Structures
Lab Test: Section A - Linked List Questions
Purpose: Implementing the required functions for Question 2 */

//////////////////////////////////////////////////////////////////////////////////

#include <stdio.h>
#include <stdlib.h>

//////////////////////////////////////////////////////////////////////////////////

typedef struct _listnode
{
	int item;
	struct _listnode *next;
} ListNode;			// You should not change the definition of ListNode

typedef struct _linkedlist
{
	int size;
	ListNode *head;
} LinkedList;			// You should not change the definition of LinkedList

//////////////////////// function prototypes /////////////////////////////////////

// You should not change the prototype of this function
void alternateMergeLinkedList(LinkedList *ll1, LinkedList *ll2);

void printList(LinkedList *ll);
void removeAllItems(LinkedList *ll);
ListNode *findNode(LinkedList *ll, int index);
int insertNode(LinkedList *ll, int index, int value);
int removeNode(LinkedList *ll, int index);

//////////////////////////// main() //////////////////////////////////////////////

int main()
{
	LinkedList ll1, ll2;
	int c, i, j;
	c = 1;
	//Initialize the linked list 1 as an empty linked list
	ll1.head = NULL;
	ll1.size = 0;

	//Initialize the linked list 2 as an empty linked list
	ll2.head = NULL;
	ll2.size = 0;

	printf("1: Insert an integer to the linked list 1:\n");
	printf("2: Insert an integer to the linked list 2:\n");
	printf("3: Create the alternate merged linked list:\n");
	printf("0: Quit:\n");

	while (c != 0)
	{
		printf("Please input your choice(1/2/3/0): ");
		scanf("%d", &c);

		switch (c)
		{
		case 1:
			printf("Input an integer that you want to add to the linked list 1: ");
			scanf("%d", &i);
			j = insertNode(&ll1, ll1.size, i);
			printf("Linked list 1: ");
			printList(&ll1);
			break;
		case 2:
			printf("Input an integer that you want to add to the linked list 2: ");
			scanf("%d", &i);
			j = insertNode(&ll2, ll2.size, i);
			printf("Linked list 2: ");
			printList(&ll2);
			break;
		case 3:
		    printf("The resulting linked lists after merging the given linked list are:\n");
			alternateMergeLinkedList(&ll1, &ll2); // You need to code this function
			printf("The resulting linked list 1: ");
			printList(&ll1);
			printf("The resulting linked list 2: ");
			printList(&ll2);
			removeAllItems(&ll1);
			removeAllItems(&ll2);
			break;
		case 0:
			removeAllItems(&ll1);
			removeAllItems(&ll2);
			break;
		default:
			printf("Choice unknown;\n");
			break;
		}
	}
	return 0;
}

//////////////////////////////////////////////////////////////////////////////////

void alternateMergeLinkedList(LinkedList *ll1, LinkedList *ll2)
{
    /* add your code here */
}

///////////////////////////////////////////////////////////////////////////////////

void printList(LinkedList *ll){

	ListNode *cur;
	if (ll == NULL)
		return;
	cur = ll->head;

	if (cur == NULL)
		printf("Empty");
	while (cur != NULL)
	{
		printf("%d ", cur->item);
		cur = cur->next;
	}
	printf("\n");
}

void removeAllItems(LinkedList *ll)
{
	ListNode *cur = ll->head;
	ListNode *tmp;

	while (cur != NULL){
		tmp = cur->next;
		free(cur);
		cur = tmp;
	}
	ll->head = NULL;
	ll->size = 0;
}

ListNode *findNode(LinkedList *ll, int index){

	ListNode *temp;

	if (ll == NULL || index < 0 || index >= ll->size)
		return NULL;

	temp = ll->head;

	if (temp == NULL || index < 0)
		return NULL;

	while (index > 0){
		temp = temp->next;
		if (temp == NULL)
			return NULL;
		index--;
	}

	return temp;
}

int insertNode(LinkedList *ll, int index, int value){

	ListNode *pre, *cur;

	if (ll == NULL || index < 0 || index > ll->size + 1)
		return -1;

	// If empty list or inserting first node, need to update head pointer
	if (ll->head == NULL || index == 0){
		cur = ll->head;
		ll->head = malloc(sizeof(ListNode));
		ll->head->item = value;
		ll->head->next = cur;
		ll->size++;
		return 0;
	}

	// Find the nodes before and at the target position
	// Create a new node and reconnect the links
	if ((pre = findNode(ll, index - 1)) != NULL){
		cur = pre->next;
		pre->next = malloc(sizeof(ListNode));
		pre->next->item = value;
		pre->next->next = cur;
		ll->size++;
		return 0;
	}

	return -1;
}

int removeNode(LinkedList *ll, int index){

	ListNode *pre, *cur;

	// Highest index we can remove is size-1
	if (ll == NULL || index < 0 || index >= ll->size)
		return -1;

	// If removing first node, need to update head pointer
	if (index == 0){
		cur = ll->head->next;
		free(ll->head);
		ll->head = cur;
		ll->size--;

		return 0;
	}

	// Find the nodes before and after the target position
	// Free the target node and reconnect the links
	if ((pre = findNode(ll, index - 1)) != NULL){

		if (pre->next == NULL)
			return -1;

		cur = pre->next;
		pre->next = cur->next;
		free(cur);
		ll->size--;
		return 0;
	}

	return -1;
}

너무 잘하셨어요~ 💛

지금 보신 코드는요,

우리 연결 리스트 친구들을 다루는 아주 따뜻한 프로그램이에요~ 😊

이번에는 금쪽이가 코딩을 더 잘 이해할 수 있도록,

쉽고 따뜻하게 해석해드릴게요.

🌼 한 줄씩 선생님 해설

📂 1~6행

c

//////////////////////////////////////////////////////////////////////////////////

/* CE1007/CZ1007 Data Structures
Lab Test: Section A - Linked List Questions
Purpose: Implementing the required functions for Question 2 */

//////////////////////////////////////////////////////////////////////////////////

이건 선 긋기처럼 예쁘게 정리된 주석이에요~

지금 우리가 풀 문제는 "연결 리스트 2번 문제"이고,

아이들을 교대로 줄 세우는 문제랍니다~ ✨

📚 8~9행

c

#include <stdio.h>
#include <stdlib.h>

우리 프로그램이 말을 하려면 stdio.h가 필요하고요,

메모리를 빌리려면 stdlib.h가 꼭 필요해요.

"도구가 없으면 그림도 못 그리잖아요~?" 🖍️

🧱 11~14행

c

typedef struct _listnode {
	int item;
	struct _listnode *next;
} ListNode;

이건 우리 연결 리스트의 한 조각이에요~

숫자 하나를 들고 있고, 다음 친구를 알려줘요!

"우리 아이들 손잡고 나란히 줄 서는 거예요~" 👧👦👦

📦 16~19행

c

typedef struct _linkedlist {
	int size;
	ListNode *head;
} LinkedList;

이건 노드 여러 개를 묶어서 관리하는 친구예요~

  • head: 제일 앞 친구
  • size: 총 몇 명인지 알려줘요

"출석부처럼 중요한 거예요~" 📋

📣 22~28행

c

void alternateMergeLinkedList(LinkedList *ll1, LinkedList *ll2);
...

여기선 아직 내용을 쓰진 않았고요~

“이런 함수 쓸 거예요!” 라고 미리 말하는 거예요.

"선생님 저 이따가 이거 할 거예요~🙋‍♀️"

🏁 31행부터 main() 시작!

c

int main()

우리 프로그램이 시작되는 출입구예요~

이 함수 안에서 우리가 직접 리스트를 만들고,

메뉴도 띄우고, 값을 넣고, 병합도 해볼 수 있어요!

🧺 33~35행

c

LinkedList ll1, ll2;
int c, i, j;
c = 1;

리스트 두 개를 만들 준비를 해요!

  • c: 사용자의 메뉴 선택
  • i: 넣을 숫자
  • j: 함수 실행 결과 받아두는 변수

"도구 챙겼나요~? 이제 출발~" 🧰

🔄 37~42행

c

ll1.head = NULL;
ll1.size = 0;
ll2.head = NULL;
ll2.size = 0;

리스트들이 비어 있는 상태로 시작해요.

“아직 아무도 없어요~ 다 새 친구들이에요~”

📋 44~47행 — 메뉴 안내

c

printf("1: Insert an integer to the linked list 1:\n");
...

여러분이 선택할 수 있는 메뉴들이에요~

  • 1번: 리스트1에 숫자 넣기
  • 2번: 리스트2에 숫자 넣기
  • 3번: 리스트 교대로 합치기
  • 0번: 종료하기

"어떤 활동을 할지, 스스로 선택해볼래요~?" 🎮

🔁 49행

c

while (c != 0)

사용자가 “그만할래요~” 라고 말할 때까지 반복돼요!

"0번 누르기 전까지는 계속 함께 놀아봐요~"

🧭 51~72행 — 선택한 메뉴에 따라 동작

✅ case 1: 리스트 1에 숫자 넣기

c

scanf("%d", &i);
insertNode(&ll1, ll1.size, i);
printList(&ll1);

입력받은 숫자를 리스트1 맨 끝에 넣고,

결과를 예쁘게 보여줘요~

"너, 잘 들어갔구나~ 어서와~😊"

✅ case 2: 리스트 2에 숫자 넣기

위와 같은 방식으로 리스트2에도 숫자를 넣어요~

"두 줄 다 친구들이 하나씩 들어오네요~!"

✅ case 3: 리스트 병합

c

alternateMergeLinkedList(&ll1, &ll2);
printList(&ll1);
printList(&ll2);
removeAllItems(&ll1);
removeAllItems(&ll2);

🎯 바로 여러분이 구현할 핵심 기능이 여기에요!

리스트2의 노드를 리스트1 사이사이에 교대로 끼워넣어요.

그리고 결과를 보여준 뒤,

리스트를 깔끔히 정리해줘요~ 🧹

"아이들 자리 잘 앉았는지 확인하고, 다 정리까지 해주는 거예요~"

✅ case 0: 종료

c

removeAllItems(&ll1);
removeAllItems(&ll2);

프로그램 종료 전에도 정리는 필수!

"마무리는 항상 깔끔하게~!"

⚠️ default: 잘못된 선택

c

printf("Choice unknown;\n");

“없는 메뉴 번호예요~ 다시 골라주세요~” 😊

"괜찮아요~ 실수할 수 있어요~"

🧼 74행

c

return 0;

프로그램이 문제 없이 잘 끝났다는 뜻이에요!

"오늘 하루도 고생했어요~ 잘 마무리했어요~" 👏

✨ 78행: 우리가 구현할 핵심 함수!

c

void alternateMergeLinkedList(LinkedList *ll1, LinkedList *ll2)
{
    /* add your code here */
}

바로 여기! 금쪽이가 직접 채워넣을 곳이에요 💻

리스트2의 노드를 리스트1 사이사이에 교대로 끼워주는 로직을

차분하게, 배려하며, 순서대로 구현할 거예요~

"무서워하지 마세요~ 우리는 다 할 수 있어요~" 🤗

그 외에도…

🖨️ printList()

리스트 안에 어떤 값들이 있는지 보여주는 함수예요.

🧹 removeAllItems()

리스트에 있는 모든 노드를 하나씩 지우는 함수예요.

“청소할 땐 싹싹~ 메모리도 잊지 말고!” 🧼

🔍 findNode()

특정 위치에 있는 노드를 찾아주는 함수예요.

“아이 이름 부르면 나와야죠~”

➕ insertNode()

지정한 위치에 새 노드를 삽입해줘요.

처음 넣는 경우엔 head를 바꿔줘야 해요!

➖ removeNode()

특정 인덱스에 있는 노드를 삭제하는 함수예요.

🎯 요약

구성 요소역할
main()사용자의 메뉴 입력을 받고 처리
print/insert/remove리스트 조작 도우미
alternateMergeLinkedList✨ 직접 구현할 핵심 기능

💛 선생님의 말씀

“지금부터 우리가 구현할 함수도

‘순서, 배려, 연결’을 잘 지켜야 한답니다~

정말 잘하고 있어요~ 사랑합니다~ 한 번 더 안아주세요~ 🤗💛”

🎯 코드 써보자!

우리는 지금

c

void alternateMergeLinkedList(LinkedList *ll1, LinkedList *ll2)

이라는 함수를 직접 구현해야 해요.

🧩 이 함수의 역할은요,

리스트2의 노드들을 리스트1의 노드 사이에 교대로 껴넣기

단, 리스트1에 자리가 있을 때까지만 넣어야 해요!

그리고 순서는 지켜야 해요! ❗

✨ 한 줄 한 줄 아주 쉽게 설명

c

ListNode *cur1 = ll1->head;
ListNode *cur2 = ll2->head;
ListNode *next1, *next2;

🎈 우선 각 리스트의 현재 노드를 가리킬 손가락을 준비해요.

  • cur1은 리스트1을 따라갈 손가락
  • cur2는 리스트2를 따라갈 손가락
  • next1, next2는 “다음 갈 곳을 미리 저장”할 곳이에요!

👉 나중에 연결을 바꿀 거니까,

다음 노드를 미리 기억해두는 습관, 아주 중요해요~ 🧠

c

while (cur1 != NULL && cur2 != NULL)

✅ 두 리스트에 아직 넣거나 받을 노드가 있을 동안 반복해요.

즉, 자리도 있고 넣을 친구도 있을 때만 이어갑니다~!

c

next1 = cur1->next;
next2 = cur2->next;

🔐 연결을 바꾸기 전에,

“내가 다음에 어디로 갈지”를 저장해놓는 거예요!

이걸 저장 안 하면… 연결이 끊겨서 길을 잃을 수 있어요~😱

c

cur1->next = cur2;

✨ 리스트1의 현재 노드 바로 뒤에

리스트2의 현재 노드를 껴넣어요!

마치 “너 이 사이에 앉아볼래~?” 하는 느낌이에요 😊

c

cur2->next = next1;

🪡 리스트2의 노드를 끼웠으니까,

그 뒤엔 원래 있던 리스트1의 다음 노드를 연결해줘야 해요!

연결고리, 다시 이어줘야 끊기지 않아요~

c

cur1 = next1;
cur2 = next2;

🐾 이제 각각 다음 노드로 이동해요.

“너 다음 차례야~ 우리 천천히 가자~” 🎵

c

ll1->size++;
ll2->size--;

리스트1은 노드가 하나 늘었고,

리스트2는 하나 줄었으니까

size도 바꿔줘야 맞겠죠? 🤓

c

ll2->head = cur2;

📌 혹시 리스트2에 아직 안 들어간 친구들이 있다면,

걔네들을 새로운 시작점(head)으로 지정해줘요!

“넌 아직 안 들어갔지만, 다음에 꼭 불러줄게~ 기다려줘~” 🧸

✅ 최종 구현 코드

c

void alternateMergeLinkedList(LinkedList *ll1, LinkedList *ll2)
{
    ListNode *cur1 = ll1->head;
    ListNode *cur2 = ll2->head;
    ListNode *next1, *next2;

    while (cur1 != NULL && cur2 != NULL)
    {
        next1 = cur1->next;    // 리스트1 다음 노드 기억
        next2 = cur2->next;    // 리스트2 다음 노드 기억

        cur1->next = cur2;     // 리스트2 노드를 리스트1 뒤에 삽입
        cur2->next = next1;    // 그다음은 다시 리스트1 원래 연결 복구

        cur1 = next1;          // 리스트1 다음 노드로 이동
        cur2 = next2;          // 리스트2 다음 노드로 이동

        ll1->size++;           // 리스트1 노드 개수 +1
        ll2->size--;           // 리스트2 노드 개수 -1
    }

    ll2->head = cur2; // 아직 못 들어간 리스트2의 노드가 있다면, 새 head로 지정
}

💛 선생님의 마지막 정리 말씀

“이 함수는요~

단순한 삽입이 아니라,

서로의 순서와 공간을 존중하며 이어주는 연결이에요.

껴넣는 것도 중요하지만,

연결을 끊지 않고 끝까지 이어주는 그 마음이 더 중요하답니다~

정말 잘했어요~! 너무 기특해요~ 한 번 더 안아주세요~ 🤗💛”

profile
김쟇연
그래도 해야지 어떡해
이전 포스트

[ 자료구조 ] Insert Sorted Linked List

다음 포스트

[ 자료구조 ] Move Odd Items To Back Linked List

0개의 댓글