[자료구조] 연결리스트 역순 연산

리스트 역순 만들기

Node *reverse(Node *head)
{  // 순회 포인터로 p, q, r을 사용
   Node *p, *q, *r;
   p = head; 	// p는 현재 가리키는 노드, q는 이전 노드
   q = NULL; 	
   while (p != NULL){
       r = q;  		//  r은 q, q는 p를 차례로 따라간다.
       q = p;
       p = p->link;	// p를 미리 옮겨 놓자.
       q->link = r;      	// q의 링크 방향을 바꾼다.
    }
    head = q; 	// q는 역순으로 된 리스트의 헤드 포인터
    return head; 	
}

 

예제) 연결 리스트 역순 만들기 

 #include <iostream>
using namespace std;

class Node {
public:
	int score; //점수
	Node *link; //다음 노드 주소
};
Node *Head = NULL;

//리스트 마지막에 노드 삽입 방법
void insert_at_rear(Node *new_node) {
	if (Head == NULL) {
		Head = new_node;
	}
	else {
		//마지막 노드를 찾고, 그 노드 뒤에 new_node 연결
		Node *list = Head; //list는 포인터이며 초기값은 head
		while (list->link != NULL) //list의 link값이 null일 경우 끝남 
			list = list->link;
		list->link = new_node;
	}
}

//리스트 처음에 노드 삽입 방법
void insert_node_at_front(Node *new_node)
{
	new_node->link = Head;
	Head = new_node;
}

Node *MakeNewNode(int score) { //노드를 하나 동적 할당, 값 초기화
	Node *ptr;
	ptr = new Node();
	ptr->score = score;
	ptr->link = NULL;
	return ptr;
}

void printNodes() {
	for (Node *list = Head; list != NULL; list = list->link)
		//list != NULL 뜻: 리스트가 뭔가를 가리키고 있으면. list == NULL 뜻: 리스트가 가리키는 방이없다는 뜻
		cout << list->score << endl;
}

void findNode(int score) {
	for (Node *list = Head; list; list = list->link)
		//C언어에서는 0만을 거짓으로 본다. 따라서 list != NULL을 그냥 list로 쓰는 경우도 있다.
		if (list->score == score)
			cout << "I found it : " << list->score << endl;
}

//리스트 역순 만들기
void reverseList() {
	Node *p, *q, *r;
	p = Head; 	// p는 현재 가리키는 노드, q는 이전 노드
	q = NULL; //r = NULL;
	while (p != NULL) {
		r = q;  		//  r은 q, q는 p를 차례로 따라간다.
		q = p;
		p = p->link;	// p를 미리 옮겨 놓자.
		q->link = r;      	// q의 링크 방향을 바꾼다.
	}
	Head = q; 	// q는 역순으로 된 리스트의 헤드 포인터
	//return Head; 
}

void main() {
	Node *new_node;
	int std_num; //학생수

	cout << "Student Number : ";
	cin >> std_num; //학생 수 입력

	for (int i = 0; i < std_num; i++)
	{
		int score;
		cout << "Student #" << i + 1 << " : ";
		cin >> score;

		//노트 생성, 연결리스트에 추가
		new_node = MakeNewNode(score);
		insert_at_rear(new_node);

	}
	printNodes();
	
	reverseList();

	cout << "AFTER REVERSING" << endl;
	printNodes();
}