C++ Data Structure: Đảo ngược danh sách liên kết tròn

Chủ đề: Thuật toán lập trình và cấu trúc dữ liệu.

Cách đảo ngược một danh sách liên kết tròn

Đầu vào là một danh sách liên kết tròng với kích thước n.

Đầu ra thực hiện nhiệm vụ đảo ngược chiều của danh sách liên kết như hình minh họa sau

Code Minh Họa

#include "stdafx.h"
#include <iostream>
#include <conio.h>

using namespace std;

// Make Node Struct
struct Node 
{
	int data;
	Node* next;
};


Node* getNode(int data)
{
	Node* newNode = new Node;

	newNode->data = data;
	newNode->next = NULL;
	return newNode;
}


void ImpReverse(Node** head_ref)
{
	if (*head_ref == NULL)
		return;

	Node* prev = NULL;
	Node* current = *head_ref;
	Node* next;
	do 
	{
		next = current->next;
		current->next = prev;
		prev = current;
		current = next;
	} 
	while (current != (*head_ref));

	(*head_ref)->next = prev;
	*head_ref = prev;
}

void ShowList(Node* head)
{
	if (head == NULL)
		return;

	Node* temp = head;
	do 
	{
		std::cout << temp->data << " ";
		temp = temp->next;
	} 
	while (temp != head);
}


int main()
{
	// Make circular list (1, 2, 3, 4)
	Node* head = getNode(1);
	head->next = getNode(2);
	head->next->next = getNode(3);
	head->next->next->next = getNode(4);
	head->next->next->next->next = head;

	cout << "Danh sach lien ket tron ban dau: ";
	ShowList(head);

	ImpReverse(&head);

	cout << "\nDanh sach lien ket trong sau khi dao nguoc: ";
	ShowList(head);

	_getch();
	return 0;
}