【说明】:
本文是左程云老师所著的《程序员面试代码指南》第二章中“反转单向和双向链表”这一题目的C++复现。
本文只包含问题描述、C++代码的实现以及简单的思路,不包含解析说明,具体的问题解析请参考原书。
感谢左程云老师的支持。
【题目】:
分别实现反转单向链表和反转双向链表的函数。
【要求】:
如果链表长度为 N,时间复杂度要求为 O(N),额外的空间复杂度要求为 O(1)。
【思路】:
链表的反转用到了三个节点指针,分别为:当前(head)、之前(pre)、之后(next)。
【编译环境】:
CentOS6.7(x86_64)
gcc 4.4.7
【实现】:
实现及测试代码:
1 /*
2 *文件名:lists_reverse.cpp
3 *作者:
4 *摘要:反转单双向链表
5 */
6
7 #include <iostream>
8
9 using namespace std;
10
11 struct SingleNode
12 {
13 int value;
14 SingleNode *next;
15 };
16
17 struct DoubleNode
18 {
19 int value;
20 DoubleNode *pre;
21 DoubleNode *next;
22 };
23
24 SingleNode* reverseList(SingleNode *head)
25 {
26 SingleNode *pre = NULL;
27 SingleNode *next = NULL;
28 //head为当前,pre为之前,next为之后
29 while(NULL != head)
30 {
31 next = head->next;
32 head->next = pre;
33 pre = head;
34 head = next;
35 }
36 return pre;
37 }
38
39 DoubleNode* reverseList(DoubleNode *head)
40 {
41 DoubleNode *pre = NULL;
42 DoubleNode *next = NULL;
43
44 while(NULL != head)
45 {
46 next = head->next;
47 head->next = pre;
48 head->pre = next; //多了一步前置处理
49 pre = head;
50 head = next;
51 }
52 return pre;
53 }
54
55 void printList(SingleNode *head)
56 {
57 while(NULL != head)
58 {
59 cout << head->value << " ";
60 head = head->next;
61 }
62 cout << endl;
63 }
64
65 void printList(DoubleNode *head)
66 {
67 while(NULL != head)
68 {
69 cout << head->value << " ";
70 head = head->next;
71 }
72 cout << endl;
73 }
74
75 int main()
76 {
77 SingleNode *shead = NULL;
78 SingleNode *sptr;
79 DoubleNode *dhead = NULL;
80 DoubleNode *dptr;
81 for(int i =0;i<10;i++)
82 {
83 if(NULL == shead && NULL == dhead)
84 {
85 shead = new SingleNode;
86 shead->value = i;
87 shead->next = NULL;
88 sptr = shead;
89
90 dhead = new DoubleNode;
91 dhead->value = i;
92 dhead->next = NULL;
93 dhead->pre = NULL;
94 dptr = dhead;
95 continue;
96 }
97 sptr->next = new SingleNode;
98 sptr = sptr->next;
99 sptr->value = i;
100 sptr->next = NULL;
101
102 dptr->next = new DoubleNode;
103 dptr->next->pre = dptr;
104 dptr = dptr->next;
105 dptr->value = i;
106 dptr->next = NULL;
107 }
108 cout << "SingleNode before reversed: " << endl;
109 printList(shead);
110 cout << "SingleNode after reversed: " << endl;
111 shead = reverseList(shead);
112 printList(shead);
113
114 cout << "DoubleNode before reversed: " << endl;
115 printList(dhead);
116 cout << "DoubleNode after reversed: " << endl;
117 dhead = reverseList(dhead);
118 printList(dhead);
119 return 0;
120 }
View Code
注:
转载请注明出处;
转载请注明源思路来自于左程云老师的《程序员代码面试指南》。
原文链接: https://www.cnblogs.com/PrimeLife/p/5358207.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/231508
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!