判断单链表的对称性

问题描述 :

设带头结点的单链表的头指针为head，结点结构由data和next两个域构成，其中data域为int型。请设计一个算法判断该链表的前m个结点的data域是否中心对称。例如xx, xyx, xyyx都是中心对称。如果m超过链表的长度，则只需要链表中的数据元素对称即认为对称。

（说明：所编代码的单链表可以没有头结点，但是如果不是单链表则不得分，比如使用数组、vector、或者双向链表，都不得分）

输入说明 :

第一行为链表元素的个数n

第二行输入单链表的数据元素（数据元素之间以空格分隔）

第三行为m

输出说明 :

输出一个字符：

T（表示对称）

F（表示不对称）

输入范例 :

10
1 2 3 2 1 1 2 3 4 5
5

输出范例 :

T

解析：

利用栈将前半段加入，后半段对比
需要注意：是否超过总个数，是否为奇数个。

代码：

#include<iostream>#include<vector>#include <algorithm>#include<stack>using namespace std;struct ListNode{int val;ListNode *next;ListNode() : val(0), next(NULL) {}ListNode(int x) : val(x), next(NULL) {}ListNode(int x, ListNode *next) : val(x), next(next) {}};class Solution {
public://判断对称性bool isSym(ListNode *head,int m){if(head==NULL)return true;int mid=m/2;ListNode *p=head;int count=0;//获取链表长度while(p){count++;p=p->next;}if(count<m){mid=count/2;}int i=0;p=head;stack<int> stk;//存入前半段while(i<mid){stk.push(p->val);p=p->next;i++;}//奇数个后移一位if(m>count){if(count%2==1){p=p->next;}}else if(m%2==1){p=p->next;}//与后半段对比while(!stk.empty()){int a=stk.top();//cout<//cout<val<if(a==p->val){p=p->next;stk.pop();}elsereturn false;}//对比完成return true;}
};//创建无头节点链表
ListNode *createByTail(){ListNode *head;ListNode *p1,*p2;int n=0,num;int len;cin>>len;head=NULL;while(n<len && cin>>num){p1=new ListNode(num);n=n+1;if(n==1)head=p1;elsep2->next=p1;p2=p1;}return head;}int main(){int m;//创建链表ListNode* head = createByTail();//判断范围cin>>m;bool res=Solution().isSym(head,m);if(res)cout<<"T";elsecout<<"F";return 0;}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！