题目
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?
思路
利用双指针法找到链表中点位置,链表中点以后的的元素(不包括中点元素)翻转,再跟链表中点位置以前的元素一一匹配。
代码
#include <iostream>
#include <vector>
using namespace std;
struct ListNode{
int val;
ListNode *next;
ListNode(int x):val(x),next(NULL){}
};
class Solution {
public:
bool isPalindrome(ListNode* head) {
if(head == nullptr){
return true;
}
ListNode* slow = head;
ListNode* fast = head->next;
while(fast && fast->next){
slow = slow->next;
fast = fast->next->next;
}
slow = slow->next;
ListNode* q = ReverseList(slow);
ListNode* p = head;
while(p && q){
if(p->val != q->val){
return false;
}
p = p->next;
q = q->next;
}
return true;
}
private:
ListNode* ReverseList(ListNode* head){
if(head == nullptr){
return head;
}
ListNode* dummy = new ListNode(-1);
ListNode* p = head;
ListNode* nextNode = p->next;
while(p){
nextNode = p->next;
p->next = dummy->next;
dummy->next = p;
p = nextNode;
}
return dummy->next;
}
};
int main(){
Solution s;
ListNode* head = new ListNode(1);
ListNode* node2 = new ListNode(2);
ListNode* node3 = new ListNode(3);
ListNode* node4 = new ListNode(4);
ListNode* node5 = new ListNode(3);
ListNode* node6 = new ListNode(2);
ListNode* node7 = new ListNode(1);
head->next = node2;
node2->next = node3;
node3->next = node4;
node4->next = node5;
node5->next = node6;
node6->next = node7;
bool result = s.isPalindrome(head);
if(result){
cout<<"是回文串"<<endl;
}
else{
cout<<"不是回文串"<<endl;
}
return 0;
}
运行时间
<script type="text/javascript">
$(function () {
$('pre.prettyprint code').each(function () {
var lines = $(this).text().split('\n').length;
var $numbering = $('<ul/>').addClass('pre-numbering').hide();
$(this).addClass('has-numbering').parent().append($numbering);
for (i = 1; i <= lines; i++) {
$numbering.append($('<li/>').text(i));
};
$numbering.fadeIn(1700);
});
});
</script>
分享到:
相关推荐
方法1 思路:将链表中的元素都保存list中,并判断这个list和反转后的list,是否相同,如果相同,则回文;否则,则不回文。...# Definition for singly-linked list. # class ListNode(object): # def __i
* [Linked List](https://github.com/kamyu104/LeetCode#linked-list) * [Stack](https://github.com/kamyu104/LeetCode#stack) * [Queue](https://github.com/kamyu104/LeetCode#queue) * [Heap]...
Given a string, find the length of the longest substring without repeating characters. Examples: Given "abcabcbb", the answer is "abc", which the length is 3. Given "bbbbb", the answer is "b", with...
leetcode 2 sum c LeetCode 帮助文档 帮助文档存放在Help文件夹下。 文件名 文件描述 ...complexitypython.txt Python的一些常规操作的复杂度统计 ...Linked List(链表) ...List ...Linked ...Palindrome Linked List
234.Palindrome 链表: | 725. 分部分拆分链表: | 328.奇偶链表:| 哈希表: 问题及解决方法: 1.二和:| 594.最长和谐子序列:| 128.最长连续序列:| 数组和矩阵 问题及解决方法: 283.移零:| 566.重塑矩阵: | ...
leetcode中325题python leetcode 以 参考 和 Hash相关 1_两数之和 387_字符串中的第一个唯一字符 链表操作 2 ...删除链表的倒数第N个节点 ...remove-duplicates-from-sorted-list ...palindrome-linked-list 双指针遍历/滑动
Palindrome linked list Linked List Cycle trees Convert Sorted Array to Binary Search Tree string and search First Bad Version Dynamic Programing *** Climbing Stairs Set Matrix Zeroes API System....
List.md) - 2015-10-06 [数字一](md/数字一.md) - 2015-10-06 [使用栈实现队列](md/使用栈实现队列.md) - 2015-10-06 [BST 中的第 K 个最小元素](md/BST.md 中的第 K 个最小元素) - 2015-09-22 [Majority Element II...
Palindrome Linked List 字符串 Valid Palindrome Implement strStr() String to Integer (atoi) Add Binary Longest Palindromic Substring Regular Expression Matching Wildcard Matching Longest Common Prefix ...
linked-list-cycle-ii 链表 linked-list-cycle 链表 copy-list-with-random-pointer 复杂度 single-number 动态规划 candy 贪心 gas-station 动态规划 palindrome-partitioning-ii 动态规划 triangle 树 sum-root-to...
leetcode 面试清单 Java 比较器与比较器 哈希 静止的 例外 线 泛型 算法 链表 Linked List Cycle Remove Nth Node From End of List Merge Two Sorted Lists 两个链表的交集 Remove Duplicates from Sorted List ...
Palindrome Number C++ 2016/4/26 Easy 044 Wildcard Matching Python 2016/4/1 Hard 051 N-Queens C++ 2016/5/18 Hard 092 Reverse Linked List II Python 2017/11/28 Medium 095 Unique Binary Search Trees ...