单链表回文结构判断-白红宇

单链表回文结构判断

阅读量：4180 次

发布时间：2019-05-26

本文共 1543 字，大约阅读时间需要 5 分钟。

题目描述：

对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。

给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。

测试样例：

1->2->2->1

返回：true

题目解析：

思路1：空间O(n) 整个链表遍历两边，开一个栈，第一遍遍历把链表中每个元素push进栈中，这样堆中的元素的pop顺序就是链表的倒序输出；第二遍就开始pop栈中数据，每pop一个数据，就把这个数据跟链表中进行对比，如果相同继续往下走，如果不同返回false。

class PalindromeList {public:    bool chkPalindrome(ListNode* A) {        // write code here		stack
   
     s;		ListNode* temp;		temp=A;		while(temp!=NULL)		{			s.push(temp->val);			temp=temp->next;		}		while(A!=NULL)		{			//cout<<"hello"<
    
     val)			{				return false;				break;			}			else				s.pop();			A=A->next;		}		return true;    }

思路2：空间O(1)，使用快慢指针法，第一步设置一个块指针和一个慢指针，快指针一次走两步，慢指针一次走一步（慢），当快指针下一步为null的时候说明慢指针已经走了一半，这就可以找到中间节点。第二步反转中间链表后面的指针，第三部从头尾向中间扫描，对比每个元素是否相等，如果都相等，则是回文数，否则不是回文数。

class PalindromeList {public:    bool chkPalindrome(ListNode* A) {        // write code here		if(A==NULL)			return false;		else if (A->next==NULL)			return true;		else{						//快慢指针找出中间节点			ListNode* quick=A;			ListNode* slow=A;			while(quick!=NULL&&quick->next!=NULL)			{				slow=slow->next;				quick=quick->next->next;			}//slow为右半段第一个元素			cout<
   
    val<
    
     next;        			ListNode* p1=p->next;        			while(p!=NULL){        				p->next=slow;				slow=p;        			    p=p1;				if(p1==NULL)					;				else					p1=p1->next;                    } 			//从头和尾向中间进行逐个比较，一旦有一个元素不等则不是			while(A!=slow)			{				if(A->val!=slow->val)					return false;				else				{					if(A->next==slow)						return true;					A=A->next;					slow=slow->next;				}			}			return true;		}	}};

转载地址：http://fohai.baihongyu.com/

你可能感兴趣的文章