234. Palindrome Linked List

Given a singly linked list, determine if it is a palindrome.

Follow up:
Could you do it in O(n) time and O(1) space?

题目大意：

判断一个单链表是否为回文链表。

思路：

找到链表中间的节点，将链表从中间分为2部分，右半部分进行链表反向转换，然后左半部分和反转后的右半部分链表进行比较。得出结果。

代码如下：

/***Definitionforsingly-linkedlist.*structListNode{*intval;*ListNode*next;*ListNode(intx):val(x),next(NULL){}*};*/classSolution{public:ListNode*reverseList(ListNode*head)//链表反转{ListNode*pre,*next;pre=NULL;next=NULL;while(head){next=head->next;head->next=pre;pre=head;head=next;}returnpre;}boolisPalindrome(ListNode*head){if(NULL==head||NULL==head->next)returntrue;intlen=0;ListNode*p=head;while(p){len++;p=p->next;}ListNode*rightListHead;rightListHead=head;intleftLen=len/2;intrightLen=len-leftLen;inti=leftLen;while(i){rightListHead=rightListHead->next;i--;}rightListHead=reverseList(rightListHead);ListNode*left=head;ListNode*right=rightListHead;while(i<leftLen){if(left->val==right->val){left=left->next;right=right->next;}else{returnfalse;}i++;}returntrue;}};

复习了单链表反转的方法。

2016-08-12 20:17:23