[TIL/크래프톤 정글9기] 36일차(C언어 링크드리스트)

이번주 WEEK05부터는 c언어를 이용하는데, 5주차는 C언어를 활용해 앞선 알고리즘에 사용했던 자료구조를 구현하는 것이 목표였다.

팀원들과 코어타임을 하면서 각자 문제를 맡아 코드를 설명하기로 했다.

frontBackSplitLL (앞뒤 분할)

문제

단일 연결 리스트를 앞쪽 절반과 뒤쪽 절반 두 개의 서브리스트로 분할합니다.

핵심 요구사항

• 리스트를 두 개로 분할
• 홀수 개수일 때 여분 원소는 앞쪽 리스트로
• 두 결과 리스트 출력

함수 프로토타입

void frontBackSplitLL(LinkedList *ll, LinkedList *resultFrontList, LinkedList *resultBackList);

동작 예시

입력: 2 → 3 → 5 → 6 → 7 (5개 노드)

결과:
frontList: 2 → 3 → 5 (3개 노드)
backList:  6 → 7     (2개 노드)

아래와 같이 이미 있는 코드를 활용하여 함수를 작성하면 되는데 이제 frontBackSplitLL에 대해 설명해보겠다.

절반으로 나누는 방법은 두 가지가 있다.

• 미드 값을 구하고 반복문을 2개를 돌려 resultFrontList, resultBackList에 노드를 삽입하는 방법
• slow, fast 방법을 사용해 미드 값을 구하고 포인터를 활용하여 resultFrontList, resultBackList 구하기

첫 번째

void frontBackSplitLinkedList(LinkedList *ll, LinkedList *resultFrontList, LinkedList *resultBackList)
{
	if (ll == NULL || ll->size == 0)
	return;
	
	// 미드값 구하기
	int midCount = (ll->size + 1) / 2;

	// 첫번째 리스트
	for (int i=0;i<midCount;i++){
	ListNode *node = findNode(ll, i);
	insertNode(resultFrontList, resultFrontList->size, node->item);
	}

	// 두 번째 리스트
	for (int i=midCount;i<ll->size;i++){
	ListNode *node = findNode(ll, i);
	insertNode(resultBackList, resultBackList->size, node->item);
	}
}

int midCount = (ll->size + 1) / 2;

미드 값을 구하기 원래 리스트에 +1을 하는 이유는 홀수일 때 나눠야할 front리스트의 결과가 back에 있는 결과보다 1개가 더 많아야하기 때문이다.

	// 첫 번째 리스트
	for (int i=0;i<midCount;i++){
	ListNode *node = findNode(ll, i);
	insertNode(resultFrontList, resultFrontList->size, node->item);
	}

	// 두 번째 리스트
	for (int i=midCount;i<ll->size;i++){
	ListNode *node = findNode(ll, i);
	insertNode(resultBackList, resultBackList->size, node->item);

mid값을 기준으로 첫 번째와 두 번째의 결과에 원래 배열의 값들을 삽입해준다.

두 번째

두 번째는 일단 slow, fast를 이용하는지 알아야한다.

(첫 반복 시작 전)
List:   [1] → [2] → [3] → [4] → [5] → NULL
        ^      ^
      slow    fast

(첫 반복 후)
List:   [1] → [2] → [3] → [4] → [5] → NULL
               ^           ^
             slow        fast

(fast가 NULL 도달, 종료)
List:   [1] → [2] → [3] → [4] → [5] → NULL
                     ^
                    slow

그러므로 fast가 종료 됐을 때 Slow가 배열의 중앙값을 나타낸다.

	// 슬로우, 스타트 선언
	ListNode *slow = ll->head;
	ListNode *fast = ll->head->next;

	// 중앙값 구하기
	while (fast!=NULL && fast->next != NULL)
	{
		slow = slow->next;
		fast = fast->next->next;
	}
	
	// 
	ListNode *backStart = slow->next;
	slow->next=NULL;

	// 첫 번째, 두 번째 시작 헤드
	resultFrontList->head = ll ->head;
	resultBackList->head = backStart;
	
	ll->head = NULL;

// 슬로우, 스타트 선언
ListNode *slow = ll->head;
ListNode *fast = ll->head->next;

• 연결 리스트의 중간을 찾기 위해 slow와 fast 포인터를 초기화
• slow는 한 칸씩, fast는 두 칸씩 이동해서 중간 노드 위치를 찾는 방식

// 중앙값 구하기
while (fast != NULL && fast->next != NULL)
{
	slow = slow->next;
	fast = fast->next->next;
}

• fast가 리스트 끝에 도달할 때쯤 slow는 중간 노드에 위치

// 중간 이후 노드를 가리키는 포인터 선언
ListNode *backStart = slow->next;
slow->next = NULL;

• slow의 다음 노드가 뒤쪽 리스트의 시작점이므로 backStart로 저장
• 리스트를 두 개로 분할하기 위해 slow->next를 NULL로 설정해 앞쪽 리스트와 뒷쪽 리스트 분리

// 앞쪽, 뒤쪽 리스트의 헤드를 각각 설정
resultFrontList->head = ll->head;
resultBackList->head = backStart;

• 앞쪽 리스트는 원래 리스트의 시작점부터 slow까지
• 뒤쪽 리스트는 slow->next부터 끝까지

// 원래 리스트는 비운다
ll->head = NULL;

• 원래 리스트를 초기화해서 두 부분 리스트로 완전히 나누는 작업을 마무리

전체 코드

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

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

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

#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 frontBackSplitLinkedList(LinkedList* ll, LinkedList *resultFrontList, LinkedList *resultBackList);

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


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

int main()
{
	int c = 1, i;
	LinkedList ll;
	LinkedList resultFrontList, resultBackList;

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

	//Initialize the front linked list as an empty linked list
	resultFrontList.head = NULL;
	resultFrontList.size = 0;

	// Initialize the back linked list as an empty linked list
	resultBackList.head = NULL;
	resultBackList.size = 0;

	printf("1: Insert an integer to the linked list:\n");
	printf("2: Split the linked list into two linked lists, frontList and backList:\n");
	printf("0: Quit:\n");

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

		switch (c)
		{
		case 1:
			printf("Input an integer that you want to add to the linked list: ");
			scanf("%d", &i);
			insertNode(&ll, ll.size, i);
			printf("The resulting linked list is: ");
			printList(&ll);
			break;
		case 2:
			printf("The resulting linked lists after splitting the given linked list are:\n");
			frontBackSplitLinkedList(&ll, &resultFrontList, &resultBackList); // You need to code this function
			printf("Front linked list: ");
			printList(&resultFrontList);
			printf("Back linked list: ");
			printList(&resultBackList);
			printf("\n");
			removeAllItems(&ll);
			removeAllItems(&resultFrontList);
			removeAllItems(&resultBackList);
			break;
		case 0:
			removeAllItems(&ll);
			removeAllItems(&resultFrontList);
			removeAllItems(&resultBackList);
			break;
		default:
			printf("Choice unknown;\n");
			break;
		}
	}

	return 0;
}

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

void frontBackSplitLinkedList(LinkedList *ll, LinkedList *resultFrontList, LinkedList *resultBackList)
{
	// if (ll == NULL || ll->size == 0)
	// 	return;
	
	// // 미드값 구하기
	// int midCount = (ll->size + 1) / 2;

	// // 첫번째 리스트
	// for (int i=0;i<midCount;i++){
	// 	ListNode *node = findNode(ll, i);
	// 	insertNode(resultFrontList, resultFrontList->size, node->item);
	// }

	// // 두 번째 리스트
	// for (int i=midCount;i<ll->size;i++){
	// 	ListNode *node = findNode(ll, i);
	// 	insertNode(resultBackList, resultBackList->size, node->item);
	// }

	// 슬로우, 스타트 선언
	ListNode *slow = ll->head;
	ListNode *fast = ll->head->next;

	// 중앙값 구하기
	while (fast!=NULL && fast->next != NULL)
	{
		slow = slow->next;
		fast = fast->next->next;
	}

	// 
	ListNode *backStart = slow->next;
	slow->next=NULL;

	// 첫 번째, 두 번째 시작 헤드
	resultFrontList->head = ll ->head;
	resultBackList->head = backStart;
	
	ll->head = NULL;
}

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

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;
}