234. Palindrome Linked List(Linked List-Easy)
234. Palindrome Linked List(Linked List-Easy)
Jack_Cui
发布于 2018-01-08 15:57:35
发布于 2018-01-08 15:57:35
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?
判断一个单链表是否是回文链表。
如：[1, 2, 3, 2, 1] 就是一个回文链表，正着依次看链表中元素和反着依次看链表中元素都是一样的。
解题思路：
- 必须做的第一个步骤就是判断输入链表是否为空，或者只有一个元素。如果为空或者只有一个元素，则此链表为回文链表返回true。
- 使用快慢指针，找到链表中点。慢指针一次走一步，快指针一次走两步。
- 根据找到的链表中点，反转后半部分的链表的所有值，并与整体单链表的值从头依次比对，有一个值不同，则不是回文链表，否则为回文链表。 如输入单链表：[1, 2, 3, 2, 1]
1
反转后半部分得到的单链表：[1, 2]
Language:C
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseList(struct ListNode* head) {
struct ListNode* pre = (struct ListNode *)malloc(sizeof(struct ListNode));
struct ListNode* next = (struct ListNode *)malloc(sizeof(struct ListNode));
pre=NULL;
next=NULL;
while(head!=NULL){
next=head->next;
head->next=pre;
pre=head;
head=next;
}
return pre;
}
bool isPalindrome(struct ListNode* head) {
struct ListNode* slow = (struct ListNode *)malloc(sizeof(struct ListNode));
struct ListNode* fast = (struct ListNode *)malloc(sizeof(struct ListNode));
if(head == NULL || head->next == NULL){
return true;
}
fast = head;
slow = head;
while(fast->next && fast->next->next){
slow = slow->next;
fast = fast->next->next;
}
slow = reverseList(slow->next);
while(slow){
if(head->val != slow->val){
return false;
}
head = head->next;
slow = slow->next;
}
return true;
}Language:cpp
/**
* 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* slow = head;
ListNode* fast = head;
while(fast->next && fast->next->next){
slow = slow->next;
fast = fast->next->next;
}
slow = reverseList(slow->next);
while(slow){
if(head->val != slow->val){
return false;
}
head = head->next;
slow = slow->next;
}
return true;
}
ListNode* reverseList(ListNode* head){
ListNode* pre = NULL;
ListNode* next = NULL;
while(head!=NULL){
next=head->next;
head->next=pre;
pre=head;
head=next;
}
return pre;
}
};本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017-03-21 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读