|
单链表的逆序，本来不是算法这一部分的，怎奈何小伙伴们说，面试考的机率比较大，故此就把它跟算法放到一起了。
关于单链表逆序的基本知识点，请参加：http://blog.csdn.net/autumn20080101/article/details/7607148
当您看了上面博文的一部分，就能基本了解的时候，下面的内容应该适合您了。下面的内容是对单链表逆序的关键知识点的一个总结。
博主客人觉得，单链表最关键的是本节点有一个指向下一个节点的指针（即后继节点指针），双向链表则是本节点有一个前驱节点和一个后继节点。
单链表时通过while循环，从头节点开始，直到节点的后继节点为空时，则到达了链表的尾部。
其实，单链表逆序，靠的就是下面的关键代码：
1 while (head != NULL) {
2 //在头节点改变之前，先获取下一个节点的指针
3 next = head->Next;
4 //头节点的下一个节点要改成它的上一个节点，是一个逆转的过程
5 head->Next = prev;
6 //上一个节点前移指向头节点
7 prev = head;
8 //头节点前移指向下一个节点
9 head = next;
10 }
开发环境为：qt, c语言代码：
完整代码：
1 #include <QCoreApplication>
2
3 //定义常数值
4 #define LEN 3
5 const int MAX_NUM = 5;
6
7 //定义节点
8 //typedef struct tagNode* linkNode;
9 typedef struct tagNode{
10 int key;
11 char value[LEN];
12 struct tagNode* Next;
13 } *Node, *linkList;
14
15 //生成链表
16 linkList generateLinkList();
17 //释放链表
18 void freeLinkList(linkList list);
19 //反转链表
20 Node ReverseLinkList(Node head);
21 //打印链表
22 void printLinkList(linkList list);
23
24 int main(int argc, char *argv[])
25 {
26 QCoreApplication a(argc, argv);
27 //生成链表
28 Node head = generateLinkList();
29 printf("反转之前的链表\r\n");
30 //打印链表
31 printLinkList(head);
32 //链表反向
33 head = ReverseLinkList(head);
34 printf("反转之后的链表\r\n");
35 //打印反向后的链表
36 printLinkList(head);
37 //释放链表内存
38 freeLinkList(head);
39 return a.exec();
40 }
41 /**
42 * @函数名：generateLinkList
43 * @参数：无
44 * @返回值：链表对象指针(首节点)
45 * @用途：生成链表对象
46 * @作者：yangfy
47 */
48 linkList generateLinkList()
49 {
50 Node head, prev;
51 //头节点
52 head = (Node)malloc(sizeof(Node));
53 head->key = 1;
54 snprintf(head->value, LEN - 1, "%c", 65);
55 //prev初始指向头节点
56 prev = head;
57 //初始化链表元素
58 for(int i = 1; i < MAX_NUM; i++){
59 Node pNode = (Node)malloc(sizeof(Node));
60 //形成链表数据
61 pNode->key = i + 1;
62 pNode->Next = NULL;
63 snprintf(pNode->value, LEN - 1, "%c", 65 + i);
64 //前一个节点的下一个节点指向本节点(pNode)
65 prev->Next = pNode;
66 //把前一个节点置为本节点，进入下一个循环
67 prev = pNode;
68 }
69 return head;
70 }
71 /**
72 * @函数名：freeLinkList
73 * @参数：head：头节点指针
74 * @返回值：无
75 * @用途：链表指针内存资源的释放。
76 * @作者：yangfy
77 */
78 void freeLinkList(Node head)
79 {
80 while (head != NULL) {
81 Node next = head->Next;
82 free(head);
83 head = next;
84 }
85 }
86
87 /**
88 * @函数名：ReverseLinkList
89 * @参数：head：头节点指针
90 * @返回值：反转后头节点指针
91 * @用途：链表的反转
92 * @作者：yangfy
93 */
94 Node ReverseLinkList(Node head)
95 {
96 Node prev = NULL;
97 Node next = NULL;
98 while (head != NULL) {
99 //在头节点改变之前，先获取下一个节点的指针
100 next = head->Next;
101 //头节点的下一个节点要改成它的上一个节点，是一个逆转的过程
102 head->Next = prev;
103 //上一个节点前移指向头节点
104 prev = head;
105 //头节点前移指向下一个节点
106 head = next;
107 }
108 return prev;
109 }
110
111
112 void printLinkList(linkList list)
113 {
114 Node node = list;
115 while (node != NULL) {
116 if(node->Next != NULL)
117 printf("当前的key为：%d, 值为：%s； 下一个key为：%d, 值为%s\r\n",node->key, node->value, node->Next->key, node->Next->value);
118 else
119 printf("当前的key为：%d, 值为：%s； 下一个key为：NULL, 值为NULL\r\n",node->key, node->value);
120 node = node->Next;
121 }
122 }
|
|
|
