本文实例讲述了C++数据结构与算法之反转链表的方法。分享给大家供大家参考，具体如下：
算法概述：要求实现将一条单向链表反转并考虑时间复杂度。
算法分析：
数组法(略)：
将列表元素逐个保存进数组，之后再逆向重建列表
点评：实现逻辑最简单，需要额外的内存开销。
移动指针：
通过三个指针逐个从链表头开始逐一反转链表元素的指针
点评：不需要额外的内存开销，会改变原始链表。
递归：
以递归的方式首先找到链表尾部，再逐一反转指针
点评：不需要额外的内存开销，不会改变原始链表。
算法实现：
构建链表结构
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
/* 节点结构 */struct NODE{ int data; struct NODE* next;};/* 添加元素-压栈 */void push(NODE** head, int dat) { struct NODE* new_node = new NODE(); new_node->data = dat; new_node->next = *head; *head = new_node;}/* 添加元素-添加 */void add(NODE** head, int dat) { struct NODE* new_node = new NODE(); new_node->data = dat; new_node->next = NULL; if (*head != NULL) { struct NODE* temp = *head; while (temp->next != NULL) { temp = temp->next; } temp->next = new_node; } else { *head = new_node; }} |
移动指针
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
/* 反转列表 */void reverse(NODE** head) { struct NODE* pre = NULL; struct NODE* cur = *head; struct NODE* nxt; while (cur != NULL) { // 反转指针 nxt = cur->next; cur->next = pre; // 移动指针 pre = cur; cur = nxt; } *head = pre;} |
递归
|
1
2
3
4
5
6
7
8
9
10
11
|
/* 反转列表-复制原表返回反转表 */NODE* reverse(NODE* head) { if (head == NULL || head->next == NULL) { return head; } NODE* new_head = reverse(head->next); // 反转指针 head->next->next = head; head->next = NULL; return new_head;} |
打印链表
|
1
2
3
4
5
6
7
8
|
/* 打印队列 */void print(NODE* head) { NODE* temp = head; while (temp != NULL) { std::cout << temp->data << std::endl; temp = temp->next; }} |
完整代码如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
|
#include <iostream>/* 节点结构 */struct NODE{ int data; struct NODE* next;};/* 添加元素-压栈 */void push(NODE** head, int dat) { struct NODE* new_node = new NODE(); new_node->data = dat; new_node->next = *head; *head = new_node;}/* 添加元素-添加 */void add(NODE** head, int dat) { struct NODE* new_node = new NODE(); new_node->data = dat; new_node->next = NULL; if (*head != NULL) { struct NODE* temp = *head; while (temp->next != NULL) { temp = temp->next; } temp->next = new_node; } else { *head = new_node; }}/* 反转列表 */void reverse(NODE** head) { struct NODE* pre = NULL; struct NODE* cur = *head; struct NODE* nxt; while (cur != NULL) { // 反转指针 nxt = cur->next; cur->next = pre; // 移动指针 pre = cur; cur = nxt; } *head = pre;}/* 反转列表-复制原表返回反转表 */NODE* reverse(NODE* head) { if (head == NULL || head->next == NULL) { return head; } NODE* new_head = reverse(head->next); // 反转指针 head->next->next = head; head->next = NULL; return new_head;}/* 打印队列 */void print(NODE* head) { NODE* temp = head; while (temp != NULL) { std::cout << temp->data << std::endl; temp = temp->next; }}int main() { struct NODE* n = NULL; add(&n, 1); add(&n, 2); add(&n, 3); n = reverse(n); print(n); return 0;} |
希望本文所述对大家C++程序设计有所帮助。
原文链接：http://www.cnblogs.com/learnhow/p/6719112.html
