понедельник, 3 июня 2013 г.

Реверс связного списка

было: node1 -> node2 ->node3->NULL
стало: node3->nod2->node1->NULL

//Узел связного списка

class Node
{
public:
int m_item;
Node *m_next;

Node(int item, Node *next){m_item = item, m_next = next;}
};

Сама функция реверса списка:

Node* reverse(Node *first)
{
Node *tmp;
Node *current = first;
Node *anotherEnd = 0;

while (NULL != current)
{
tmp = current->m_next;
current->m_next = anotherEnd;
anotherEnd = current;
current = tmp;
}
return anotherEnd;  //возвращает новое начало списка
}

Отображение данных узлов:

void print(Node *first)
{
Node *tmp = first;
while (NULL != tmp)
{
cout << tmp->m_item << ' ';
tmp = tmp->m_next;
}
cout << endl;
}

Ну и main() :

int main()
{
srand(time(NULL));

Node *first = new Node(rand()%10, 0);
Node *tmp = first;
for (int i = 0; i < 8; ++i)  //Создаем список из 8 элементов
{
tmp->m_next = new Node(rand()%10, 0);
tmp = tmp->m_next;
}

print(first);

Node *end = reverse(first);
print(end);

return 0;
}