[코딩인터뷰 완전정복] 2.3 중간 노드 삭제

Q : 단방향 연결리스트가 주어졌을 때 중간에 있는 노드하나를 삭제하는 알고리즘을 작성하라. 단 삭제할 노드에만 접근 할 수 있다.

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

	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 DeleteInsideNode(node* node) {
	node->data = node->next->data;
	node->next = node->next->next;
}

int main() {
	linked_list list;
	list.add_node(1);
	list.add_node(2);
	list.add_node(1);
	node *deleteNode = list.add_node(5);
	list.add_node(4);
	list.add_node(4);
	list.add_node(1);
	list.add_node(5);

	list.printLinkedList();
	DeleteInsideNode(deleteNode);
	list.printLinkedList();
}

주어진 노드(deleteNode)의 전 노드에 접근 할 방법이 없기 때문에 일반적인 삭제는 불가능하다.

따라서 deleteNode의 next 의 내용을 deleteNode에 옳기고 next노드를 삭제한다.

마지막 노드는 이 방법을 사용할 수 없다.