[CS] 연결 리스트 뒤집기 (Reverse Linked List)

테크니컬 면접 문제의 단골인 연결 리스트(Linked List). 그 중에서도 가장 많이 나온다는 뒤집기 문제이다. 

기본적인 연결 리스트를 구현 할 줄 알아야 겠다. C/C++을 이용한다고 할 때, struct 혹은 class로 먼저 node를 정의한다. 필요한 기본 함수로는 insert, delete, print(

traverse

traverse) 정도가 되겠다. delete는 뒤집기에는 필요하지 않으므로 생략한다. 

C/C++로 구현하기 위해서는 포인터에 대해서 알아야 한다. 새 노드를 head가 가리키는 첫 노드로 삽입하는 insert를 구현하기 위해서는 포인터의 포인터(A pointer that points to a pointer)를 인자로 넘겨야 head가 가리키는 노드를 새 노드로 변경할 수 있다는 점에 주의해야 한다. 

리스트를 뒤집는 reverse 함수를 구현할 때에도 잘못 생각하면 무한 루프에 빠지게 되는데 주의해야 한다. 이전 노드, 현재 노드, 다음 노드를 테이블로 그려보고 적절히 값이 어떻게 바뀌어야 할지 생각해보면 할 수 있다.

그런데, 종이만 주고 이걸 구현하라고 하면 쉽게 완성하지는 못할 것 같다. 포인터가 아직 완전히 익숙하지 않아서 부분부분 오류를 낼 것 같다. 조금 더 다양한 것을 구현해보는 연습을 해야겠다. 

#include <iostream>

using namespace std;

typedef struct node {
	int value;
	struct node *next;
} Node;

void insert(Node **head, int value) {
	Node *newNode = (Node*)malloc(sizeof(Node));
	newNode->value = value;
	newNode->next = *head;
	*head = newNode;
}

void print(Node *head) {
	Node *curNode;
	curNode = head;
	while (curNode != NULL) {
		cout << curNode->value << " ";		
		curNode = curNode->next;
	}
	cout << endl;
}

void reverse(Node **head) {
	Node *curNode, *preNode, *tmp;
	
	preNode = NULL;
	curNode = *head;
	
	if (curNode) {
		while(curNode->next) {
			tmp = curNode->next;
			curNode->next = preNode;
			preNode = curNode;
			curNode = tmp;
		}
		curNode->next = preNode;
		*head = curNode;
	}
}

int main() {
	Node *head = NULL;

	// list w/o element
	reverse(&head);
	print(head);
	
	// list w/ one element
	insert(&head, 4);
	reverse(&head);
	print(head);

	// list w/ elements
	insert(&head, 3);	
	insert(&head, 2);
	insert(&head, 1);
	print(head);
	reverse(&head);
	print(head);
	reverse(&head);
	print(head);
}