【说明】:
本文是左程云老师所著的《程序员面试代码指南》第二章中“判断一个链表是否为回文结构”这一题目的C++复现。
本文只包含问题描述、C++代码的实现以及简单的思路,不包含解析说明,具体的问题解析请参考原书。
感谢左程云老师的支持。
【题目】:
给定一个链表的头节点 head,请判断该链表是否为回文(正反结构相同)结构。
例如:
1->2->1,返回 true
1->2->2->1,返回 true
15->6->15, 返回 true
1->2->3,返回 false
【进阶】:
如果链表长度为 N,时间复杂度达到 O(N),额外空间复杂度达到 O(1)。
【思路】:
普通解法:使用栈
进阶解法:逆序后半部分的链表,然后与前半部分依次比较
【编译环境】:
CentOS6.7(x86_64)
gcc 4.4.7
【实现】:
实现及测试代码:
1 /*
2 *文件名:lists_palindrome.cpp
3 *作者:
4 *摘要:判断一个链表是否为回文结构
5 */
6
7 #include <iostream>
8 #include <stack>
9 using namespace std;
10
11 struct Node
12 {
13 int value;
14 Node *next;
15 };
16
17 bool isPalindrome1(Node *head)
18 {
19 stack<Node> s;
20 Node *cur = head;
21 while(NULL != cur)
22 {
23 s.push(*cur); //将链表节点全部压入栈中
24 cur = cur->next;
25 }
26 while(NULL != head)
27 {
28 if(head->value != s.top().value)
29 return false;
30 s.pop();
31 head = head->next;
32 }
33 return true;
34 }
35
36 //使用栈的优化算法
37 bool isPalindrome2(Node *head)
38 {
39 if(NULL == head || NULL == head->next)
40 return true;
41 Node *right = head->next;
42 Node *cur = head;
43 while(NULL != cur->next && NULL != cur->next->next)
44 {
45 right = right->next;
46 cur = cur->next->next;
47 }
48 stack<Node> s;
49 while(NULL != right)
50 {
51 s.push(*right); //将链表的右半部分压入栈
52 right = right->next;
53 }
54 while(!s.empty())
55 {
56 if(head->value != s.top().value)
57 return false;
58 s.pop();
59 head = head->next;
60 }
61 return true;
62 }
63
64 //进阶算法
65 bool isPalindrome3(Node *head)
66 {
67 if(NULL == head || NULL == head->next)
68 return true;
69 Node *n1(head),*n2(head);
70 while(NULL != n2 && NULL != n2->next)
71 {
72 n1 = n1->next; //找到中间节点
73 n2 = n2->next->next;
74 }
75 n2 = n1->next; //右半部分的第一个节点
76 n1->next =NULL;
77 Node *n3 = NULL;
78 while(NULL != n2) //反转右半部分链表
79 {
80 n3 = n2->next;
81 n2->next = n1;
82 n1 = n2;
83 n2 = n3;
84 }
85 n3 = n1; //记录最后一个节点
86 n2 = head; //记录头节点
87 bool res = true;
88 while(NULL != n1 && NULL != n2)
89 {
90 if(n1->value != n2->value)
91 {
92 res = false;
93 break;
94 }
95 n1 = n1->next;
96 n2 = n2->next;
97 }
98 n1 = n3->next;
99 n3->next = NULL;
100 while(NULL != n1)
101 {
102 n2 = n1->next;
103 n1->next = n3;
104 n3 = n1;
105 n1 = n2;
106 }
107 return res;
108 }
109
110 void printLists(Node *head)
111 {
112 while(NULL != head)
113 {
114 cout << head->value << " " ;
115 head = head->next;
116 }
117 cout << endl;
118 }
119
120 int main()
121 {
122 Node *head1 = NULL;
123 Node *head2 = NULL;
124 Node *ptr = NULL;
125
126 for(int i =1;i<6;i++)//构造链表
127 {
128 if(NULL == head1)
129 {
130 head1 = new Node;
131 head1->value = i;
132 head1->next = NULL;
133 ptr = head1;
134 continue;
135 }
136 ptr->next = new Node;
137 ptr = ptr->next;
138 ptr->value = i;
139 ptr->next = NULL;
140 }
141 printLists(head1);
142 if(isPalindrome1(head1) && isPalindrome2(head1) && isPalindrome3(head1) )
143 cout << "Head1 is a palindrome list!" << endl;
144 else
145 cout << "Head1 is not a palindrome list!" << endl;
146 Node *right = NULL;
147 Node *tmp = NULL;
148 for(int i =1;i<5;i++)//构造回文结构的链表
149 {
150 if(NULL == head2 && NULL == right)
151 {
152 head2 = new Node;
153 head2->value = i;
154 head2->next = NULL;
155 ptr = head2;
156
157 right = new Node;
158 right->value = 5-i;
159 right->next = NULL;
160 tmp = right;
161 continue;
162 }
163 ptr->next = new Node;
164 ptr = ptr->next;
165 ptr->value = i;
166 ptr->next = NULL;
167
168 tmp->next = new Node;
169 tmp = tmp->next;
170 tmp->value =5-i;
171 tmp->next = NULL;
172 }
173 ptr->next = right;
174 printLists(head2);
175 if(isPalindrome1(head2) || isPalindrome2(head2) || isPalindrome3(head2) )
176 cout << "Head2 is a palindrome list!" << endl;
177 else
178 cout << "Head2 is not a palindrome list!" << endl;
179
180 return 0;
181 }
View Code
注:
转载请注明出处;
转载请注明源思路来自于左程云老师的《程序员代码面试指南》。
原文链接: https://www.cnblogs.com/PrimeLife/p/5367311.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/231623
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!