CC150 2.3

2_3.cpp

/* CC150 2.3
 * Implement an algorithm to delete a node in the middle of a singly linked list, given only access to that node.
 * EXAMPLE
 * Input: the node c from the linked list a->b->c->d->e
 * Result: nothing isreturned, but the new linked list looks like a->b->d->e
 */

#include <iostream>

using namespace std;

struct Node {
	int value = 0;
	Node *next =nullptr;
};

void initNode(Node *head, int n);
void appendNode(Node *head, int n);
void display(Node *head);

void deleteMiddle(Node *mid)
{
	if (mid == nullptr || mid->next == nullptr) {
		cerr << "Undeletable!" << endl;
		return;
	}
	Node *tmpNode = mid->next;
	mid->value = tmpNode->value;
	mid->next = tmpNode->next;
	delete tmpNode;
}

int main()
{
	int n;
	cin >> n; // index of element to be deleted
	int data;
	Node *head = new Node;
	if (cin >> data) { // built the list
		initNode(head, data);
		while (cin >> data) {
			appendNode(head, data);
		}
	}
	Node *del = head;
	if (n < 1)
		cerr << "Invalid index!" << endl;
	else {
		for (int i = 1; del != nullptr && i != n; ++i) // locate to the nth element (to delete)
			del = del->next;
		deleteMiddle(del); // delete node
	}
	display(head); // print the processed list
	return 0;
}

void initNode(Node *head, int n) {
	head->value = n;
	head->next = nullptr;
	return;
}

void appendNode(Node *head, int n) {
	Node *newNode = new Node;
	newNode->value = n;
	Node *curr = head;
	while (curr) {
		if (curr->next == nullptr) {
			curr->next = newNode;
			return;
		}
		else
			curr = curr->next;
	}
	return;
}

void display(Node *head) {
	for (Node *curr = head; curr != nullptr; curr = curr->next)
		cout << curr->value << " ";
	cout << endl;
	return;
}