[코딩인터뷰 완전정복] 2.4 분할

Q : 값 x가 주어졌을 때 x보다 작은 노드들을 x보다 크거나 같은 노드들보다 앞에 오도록 하는 코드를 작성하라.

만약 x가 리스트에 있다면 x는 '오른쪽 그룹' 어딘가에만 존재하면 된다.

왼쪽과 오른쪽 그룹 사이에 있을 필요는 없다.

// LinkedList.h
#include <iostream>

struct node {
	int data;
	node *next;
};

class linked_list {
private:
	node *head, *tail;
public:
	linked_list() {
		head = NULL;
		tail = NULL;
	}

	node* add_node(int n) {
		node *temp = new node;
		temp->data = n;
		temp->next = NULL;
		if (head == NULL) {
			head = temp;
			tail = temp;
		}
		else {
			tail->next = temp;
			tail = tail->next;
		}

		return temp;
	}

	void addFirst(int x) {
		node *temp = new node();
		temp->data = x;
		temp->next = head;
		head = temp;
		if (tail == NULL) tail = temp;
	}

	void addFirst(node *node) {
		node->next = head;
		head = node;
		if (tail == NULL) tail = node;
	}

	int removeFirst() {
		int data = head->data;
		head = head->next;
		return data;
	}

	node* first() {
		return head;
	}

	void printLinkedList() {
		if (head == NULL) return;

		node* currentNode = head;
		while (currentNode->next != NULL) {
			printf("%d - ", currentNode->data);
			currentNode = currentNode->next;
		}
		printf("%d", currentNode->data);

		printf("\n");
	}
};

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

void divisionBasedOnX(linked_list& list, int x) {
	node *pre = list.first();
	node *crr = list.first()->next;

	while (crr != NULL) {
		if (crr->data < x) {
			pre->next = crr->next;
			list.addFirst(crr);
			crr = pre->next;
		}
		else {
			pre = crr;
			crr = crr->next;
		}
	}
}

int main() {
	linked_list list;
	list.add_node(3);
	list.add_node(2);
	list.add_node(1);
	list.add_node(5);
	list.add_node(4);
	list.add_node(4);
	list.add_node(1);
	list.add_node(5);
	list.add_node(6);
	list.add_node(8);
	list.add_node(1);
	list.add_node(2);
	list.add_node(7);

	list.printLinkedList();
	divisionBasedOnX(list, 5);
	list.printLinkedList();
}

리스트를 순회하며 X보다 작은 값이 나오면 Node를 삭제하고 Head의 앞에 붙인다.

Head를 계속 수정해줘야 한다.

첫번째 노드는 확인할 필요가 없다. (순회가 끝나면 오른쪽과 왼쪽의 중간에 위치함)