`
SunnyYoona
  • 浏览: 361444 次
社区版块
存档分类
最新评论

[LeetCode]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?

思路

利用双指针法找到链表中点位置,链表中点以后的的元素(不包括中点元素)翻转,再跟链表中点位置以前的元素一一匹配。

代码

/*---------------------------------------
*   日期:2015-07-18
*   作者:SJF0115
*   题目: 234.Palindrome Linked List
*   网址:https://leetcode.com/problems/palindrome-linked-list/
*   结果:AC
*   来源:LeetCode
*   博客:
-----------------------------------------*/
#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;
        }//if
        // 中点位置
        ListNode* slow = head;
        ListNode* fast = head->next;
        while(fast && fast->next){
            slow = slow->next;
            fast = fast->next->next;
        }//while
        slow = slow->next;
        // 翻转
        ListNode* q = ReverseList(slow);
        // 判断是否是回文串
        ListNode* p = head;
        while(p && q){
            if(p->val != q->val){
                return false;
            }//if
            p = p->next;
            q = q->next;
        }//while
        return true;
    }
private:
    // 翻转
    ListNode* ReverseList(ListNode* head){
        if(head == nullptr){
            return head;
        }//if
        // 头结点
        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;
        }//while
        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;
    }//if
    else{
        cout<<"不是回文串"<<endl;
    }//else
    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>
分享到:
评论

相关推荐

    Leetcode 234. Palindrome Linked List

    方法1  思路:将链表中的元素都保存list中,并判断这个list和反转后的list,是否相同,如果相同,则回文;否则,则不回文。...# Definition for singly-linked list. # class ListNode(object): # def __i

    LeetCode最全代码

    * [Linked List](https://github.com/kamyu104/LeetCode#linked-list) * [Stack](https://github.com/kamyu104/LeetCode#stack) * [Queue](https://github.com/kamyu104/LeetCode#queue) * [Heap]...

    LeetCode3 Longest Substring Without Repeating Characters

    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...

    leetcode2sumc-LeetCode:LeetCode的一些题目

    leetcode 2 sum c LeetCode 帮助文档 帮助文档存放在Help文件夹下。 文件名 文件描述 ...complexitypython.txt Python的一些常规操作的复杂度统计 ...Linked List(链表) ...List ...Linked ...Palindrome Linked List

    leetcode338-Leetcode:一些过滤leetcode问题的解决方案

    234.Palindrome 链表: | 725. 分部分拆分链表: | 328.奇偶链表:| 哈希表: 问题及解决方法: 1.二和:| 594.最长和谐子序列:| 128.最长连续序列:| 数组和矩阵 问题及解决方法: 283.移零:| 566.重塑矩阵: | ...

    leetcode中325题python-leetcode:leetcode

    leetcode中325题python leetcode 以 参考 和 Hash相关 1_两数之和 387_字符串中的第一个唯一字符 链表操作 2 ...删除链表的倒数第N个节点 ...remove-duplicates-from-sorted-list ...palindrome-linked-list 双指针遍历/滑动

    leetcode卡-leetcode:利特码解决方案

    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....

    javalruleetcode-leetcode:力码解决方案

    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...

    cpp-算法精粹

    Palindrome Linked List 字符串 Valid Palindrome Implement strStr() String to Integer (atoi) Add Binary Longest Palindromic Substring Regular Expression Matching Wildcard Matching Longest Common Prefix ...

    gasstationleetcode-leetcode-in-niuke:在牛客网上的在线编程中的leetcode在线编程题解

    linked-list-cycle-ii 链表 linked-list-cycle 链表 copy-list-with-random-pointer 复杂度 single-number 动态规划 candy 贪心 gas-station 动态规划 palindrome-partitioning-ii 动态规划 triangle 树 sum-root-to...

    javalruleetcode-JavaInterviewChecklist:要检查的Java事项

    leetcode 面试清单 Java 比较器与比较器 哈希 静止的 例外 线 泛型 算法 链表 Linked List Cycle Remove Nth Node From End of List Merge Two Sorted Lists 两个链表的交集 Remove Duplicates from Sorted List ...

    leetcodepython001-Algorithm:关于数据结构和算法的问题(Leetcode、编程之美和课程作业)

    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 ...

Global site tag (gtag.js) - Google Analytics