链表逆序的循环实现和递归实现

无我

让内心永远燃烧着伟大的光明的精神之火！

灵活的思考，严谨的实现

豪迈的气魄、顽强的意志和周全的思考

链表逆序：
一个链表的结点结构
struct Node
{
int data ;
Node *next ;
};
typedef struct Node Node ;

已知链表的头结点head,写一个函数把这个链表逆序 ( Intel)。

链表逆序是笔试中链表测试的经典题，这次自己写了一下代码，分别用循环和递归方法做两种实现，记录在此。

#include <iostream>
2

using namespace std;
3

struct Node
5

{
6

int data ;
7

Node *next ;
8

};
9

//链表反序的循环实现
10

Node * ReverseList(Node *head)
11

{
12

Node * p1 = NULL;//p1代表链表被反序好的部分的头结点
13

Node * p2 = head;//p2代表链表还没有被反序部分的头结点
14

while(p2)
15

{
16

Node * pTemp = p2->next;
17

p2->next = p1;
18

p1 = p2;
19

p2 = pTemp;
20

}
21

return p1;
22

}
23

//链表反序的递归实现
24

Node * ReverseList_DG(Node *head,Node * last=NULL)
25

{
26

//last代表链表被反序好的部分的头结点,head代表链表还没有被反序部分的头结点
27

if (head == NULL) return last;
28

Node * pTemp = head->next;
29

head->next = last;
30

ReverseList_DG(pTemp,head);
31

}
32

int main(int argc, char* argv[])
34

{
35

Node * pHead = new Node,*pTemp;
36

pHead->data = 0;
37

pHead->next = NULL;
38

for (int i=1;i<10;++i)
39

{
40

pTemp = new Node;
41

pTemp->data = i;
42

pTemp->next = pHead;
43

pHead = pTemp;
44

}
45

//打印出原始链表
46

pTemp = pHead;
47

while(pTemp)
48

{
49

cout<<pTemp->data<<",";
50

pTemp = pTemp->next;
51

}
52

cout<<endl;
53

//循环法反序链表并输出
54

pHead = ReverseList(pHead);
55

pTemp = pHead;
56

while(pTemp)
57

{
58

cout<<pTemp->data<<",";
59

pTemp = pTemp->next;
60

}
61

cout<<endl;
62

//递归法反序链表并输出
63

pHead = ReverseList_DG(pHead);
64

pTemp = pHead;
65

while(pTemp)
66

{
67

cout<<pTemp->data<<",";
68

pTemp = pTemp->next;
69

}
70

cout<<endl;
71

return 0;
73

}

posted on 2012-11-05 08:44 Tim 阅读(3378) 评论(0) 编辑收藏引用所属分类: C/C++语言

只有注册用户登录后才能发表评论。


相关文章: 32位编译的程序无法使用大于2G的内存 GetConsoleWindow fputs不自动添加换行符 system、WinExec、ShellExecute、CreateProcess libevent使用中要注意的问题 Visual Studio查找中文的正则表达式非类型模板形参取数组的维数 A*算法实现链表逆序的循环实现和递归实现 dll的概念、dll导出类（转）

网站导航: 博客园 IT新闻 BlogJava 知识库博问管理

无我

链表逆序的循环实现和递归实现

导航

统计

公告

留言簿(9)

随笔分类(173)

IT

Life

搜索

积分与排名

最新随笔

最新评论

阅读排行榜