判断一个链表是否为回文结构

【说明】：

　　本文是左程云老师所著的《程序员面试代码指南》第二章中“判断一个链表是否为回文结构”这一题目的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

注：

　　转载请注明出处；

　　转载请注明源思路来自于左程云老师的《程序员代码面试指南》。