[LeetCode] Palindrome Linked List

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?

解题思路：

此题的题意为判断单向链表是否为回文。难点就是链表不能随机存取，而且不能反向遍历。

一个思想就是找到中间节点，然后将其中一部分翻转，再逐一遍历即可。

找到中间节点有两种方法，一个是先求出链表的长度，然后再找到中间节点。另外一种方法是双指针法。

方法一的代码如下：

/** * Definition for singly-linked list. * struct ListNode { *int val; *ListNode *next; *ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public:bool isPalindrome(ListNode* head) {ListNode* myHead1 = new ListNode(0);myHead1->next = head;int len = getLength(myHead1);if(len<2){return true;}bool flag = true;ListNode* myHead2 = new ListNode(0);ListNode* p = myHead1->next, *q;for(int i=len/2; i>0; i–){myHead1->next = p->next;p->next=myHead2->next;myHead2->next = p;p=myHead1->next;}p=myHead1->next;q=myHead2->next;if(len%2!=0){p=p->next;}while(p!=NULL){if(p->val!=q->val){flag = false;break;}p=p->next;q=q->next;}return flag;}//注意这里有个表头了int getLength(ListNode* head){int count = 0;while(head->next!=NULL){head=head->next;count++;}return count;}};方法二的代码如下：

/** * Definition for singly-linked list. * struct ListNode { *int val; *ListNode *next; *ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public:bool isPalindrome(ListNode* head) {if(head==NULL || head->next==NULL){return true;}ListNode* fast = head;ListNode* slow = head;while(fast!=NULL&&fast->next!=NULL){fast = fast->next->next;slow = slow->next;}//将前半部分ListNode* myHead = new ListNode(0);ListNode* p = head, *q;while(p!=slow){q = p->next;p->next = myHead->next;myHead->next = p;p = q;}p = myHead->next;q = slow;if(fast!=NULL){ //表示是奇数个q= q->next;}while(p!=NULL){if(p->val!=q->val){return false;}p=p->next;q=q->next;}return true;}};

版权声明：本文为博主原创文章，未经博主允许不得转载。

，没有行囊，没有目的，我孤独的走在路上，