Posted on 2011-06-23 17:01
亂78糟 閱讀(1411)
評論(0) 編輯 收藏 引用 所屬分類:
算法&數據結構
/***********************************
* 單向鏈表逆序
* yanzh 2011-6-23
************************************/
#include <iostream>
using namespace std;
class Node{
public:
Node(int v):value(v),next(NULL){}
int value;
Node* next;
};
Node* init_list(int n)
{
Node *head, *node, *tail;
head = tail = NULL;
for (int i = 0; i < n; i++)
{
node = new Node(i);
if (i == 0)
{
head = node;
tail = node;
}
else
{
tail->next = node;
tail = node;
}
}
return head;
}
void uninit_list(Node *head)
{
Node *node = head;
while (head != NULL)
{
node = node->next;
delete head;
head = node;
}
head = NULL;
}
void reverse_list(Node **list)
{
Node *head, *tail, *mid;
head = *list;
//一個節點，直接返回
if (head->next == NULL)
return;
//兩個節點或以上節點
mid = head->next;
head->next = NULL;
tail = mid->next;
while (tail != NULL)
{
mid->next = head;
head = mid;
mid = tail;
tail = tail->next;
}
mid->next = head;
*list = mid;
}
void output(Node *list)
{
int i = 0;
Node *node = list;
while (node != NULL)
{
cout<<"node["<<i++<<"] = "<<node->value<<endl;
node = node->next;
}
}
int main(int argc, char *argv[])
{
int len = 5;
Node *list = NULL;
if (argc > 1)
len = atoi(argv[1]);
list = init_list(len);
output(list);
reverse_list(&list);
//輸出
cout<<"\n逆序后\n"<<endl;
output(list);
uninit_list(list);
return 0;
}