[C++]Split Doubly Linked List

1. 알고리즘 설명

: 연결리스트를 반으로 나누는 중간 노드 반환

: 이때 연결리스트를 반으로 나눌 때 노드의 개수가 짝수와 홀수 상관없이 (노드의 개수/2)+1번째 노드 반환

: 노드를 2칸씩 건너뛰어 순회하는 rabbit 노드 + 노드를 1칸씩 건너뛰어 순회하는 turtle 노드로 구성

: rabbit노드가 마지막 노드이거나 tail노드를 가리킬 때의 turtle노드가 중간 노드가 됨

: rabbit 노드와 turtle 노드 모두 첫번째 노드부터 순회 시작

 

1-1. doubly linked list

2023.11.29 - [C++/자료구조] - [C++]Doubly linked list with sentinel nodes

[C++]Doubly linked list with sentinel nodes

 

1-2. 케이스 분류

: 노드의 개수에 따라 분류

홀수	짝수
rabbit은 무조건 last노드를 끝으로 가리키게 되어있음	rabbit은 무조건 tail노드를 끝으로 가리키게 되어있음

 

1-3. 구현

(1) 

main.cpp

int main(){

    Node * half = list.half();
    cout << "[중간 노드를 기준으로 노드 순회 (단, 중간 노드는 뒤에 있는 연결리스트에 덧붙임)]" << endl;
    LinkedList front;
    LinkedList back;
    list.Split(half, &front, &back);
    cout << "\n[분할된 앞쪽 연결리스트]" << endl;
    front.traverse();
    cout << "[분할된 뒷쪽 연결리스트]" << endl;
    back.traverse();

	return 0;
}​

LinkedList.h 내에 정의

	Node * half() {
		//가운데 있는 노드 반환
		Node* turtle;
		Node* rabbit;
		turtle = rabbit = begin();
		while (rabbit != end() && rabbit != last()) {
			rabbit = rabbit->getNext()->getNext();
			turtle = turtle->getNext();
		}
		return turtle;

	}

	void Split(Node * half,LinkedList * front, LinkedList * back) {
		Node* curNode = begin();
		while (curNode != half) {
			front->push_back(curNode->data);
			curNode = curNode->next;
		}
		while (curNode != end()) {
			back->push_back(curNode->data);
			curNode = curNode->next;
		}
	}​

 

(2) 구현 결과

(좌) 노드의 개수가 홀수 / (우) 노드의 개수가 짝수