[C++] 연결리스트 분할

1. 알고리즘 설명

→ 다음과 같이 연결리스트가 주어지면 두 개의 연결리스트로 나눈다
(이때, 노드의 갯수가 홀수일땐 가운데 기준 노드는 후면 연결리스트에 삽입되도록 함)
                                                                              → 짝수/홀수 케이스 나눌 필요 없어짐
 
 

1-1. 구현

Linked_list.h

#pragma once
#include <iostream>
using namespace std;
class Node {
private:
	int data;
	Node* link;
public:
	Node(int item, Node* next) :data(item), link(next) {

	}
	Node(int item) : data(item), link(NULL) {

	}
	int getData() {
		return data;
	}
	Node* getLink() {
		return link;
	}
	friend class Linked_List;
};

class Linked_List {
private:
	Node* head;
	Node* tail;
	int NodeCount;
public:
	Linked_List():head(NULL),tail(NULL),NodeCount(0) {
	}
	void insert(int item) {
		Node* newNode = new Node(item);
		if (isEmpty()) {
			head = newNode;
			tail = newNode;
		}
		else {
			tail->link = newNode;
			tail = newNode;
		}
		NodeCount++;
	}
	void traverse() {
		Node* curNode = head;
		while (curNode != NULL) {
			cout << curNode->data;
			if (curNode->link != NULL) {
				cout << " -> ";
			}
			curNode = curNode->link;
		}
		cout << endl<<endl;
	}
	int isEmpty() {
		return head == NULL;
	}

	int getCount() {
		return NodeCount;
	}
	Node* getHead() {
		return head;
	}
	Node* getTail() {
		return tail;
	}
};

main.cpp

#include "Linked_list.h"
#include <iostream>

using namespace std;


void ListToHalf(Linked_List * list,  Linked_List& front,  Linked_List& back) {
	int cnt = list->getCount();
	if (cnt == 1) {
		front.insert(list->getHead()->getData());
	}
	else {
		int half = cnt / 2;
		Node* curNode = list->getHead();
		for (int i = 0; i < cnt; i++) {
			if (i < half) {
				front.insert(curNode->getData());
			}
			else {
				back.insert(curNode->getData());
			}
			curNode = curNode->getLink();
		}
	}

}

int main() {

	Linked_List list;
	list.insert(3);
	list.insert(2);
	list.insert(4);
	list.insert(1);
	list.insert(7);
	list.insert(9);
	list.insert(8);
	cout << "[Linked_list]" << endl;
	list.traverse();

	cout << "**********분할 작업 수행***********" << endl << endl;
	Linked_List front;
	Linked_List back;
	ListToHalf(&list, front, back);
	
	cout << "[Front List]" << endl;
	front.traverse();

	cout << endl <<"[Back List]" << endl;
	back.traverse();




	getchar();
	return 0;
}