{"id":2081,"date":"2018-03-13T02:45:33","date_gmt":"2018-03-13T09:45:33","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=2081"},"modified":"2018-03-13T02:45:41","modified_gmt":"2018-03-13T09:45:41","slug":"leetcode-234-palindrome-linked-list","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/list\/leetcode-234-palindrome-linked-list\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 234. Palindrome Linked List"},"content":{"rendered":"

\u9898\u76ee\u5927\u610f\uff1a\u68c0\u67e5\u4e00\u4e2a\u5355\u5411\u94fe\u8868\u662f\u4e0d\u662f\u56de\u6587\u3002<\/p>\n

Problem:<\/strong><\/p>\n

https:\/\/leetcode.com\/problems\/palindrome-linked-list\/description\/<\/a><\/p>\n

\n
\n

Given a singly linked list, determine if it is a palindrome.<\/p>\n

Follow up:<\/b>
\nCould you do it in O(n) time and O(1) space?<\/p>\n<\/div>\n<\/div>\n

Idea: <\/strong><\/p>\n

    \n
  1. use fast \/ slow pointers to find the middle node and see whether the list has odd\/even number of elements.<\/li>\n
  2. Reverse the right half the list, and compare with the left half<\/li>\n<\/ol>\n

    E.g.
    \n1->2->3->4->3->2->1->null
    \nfast = null
    \nslow = 4
    \nslow->next = 3
    \nreverse(slow->next)
    \nnull<-3<-2<-1 compare with 1->2->3->…<\/p>\n

    Solution: 1 <\/strong><\/p>\n

    Time complexity: O(n)<\/p>\n

    Space complexity: O(1)<\/p>\n

    C++<\/p>\n

    class Solution {\r\npublic:\r\n  bool isPalindrome(ListNode* head) {\r\n    ListNode* slow = head;\r\n    ListNode* fast = head;\r\n    while (fast && fast->next) {\r\n      fast = fast->next->next;\r\n      slow = slow->next;\r\n    }\r\n    \/\/ if fast != nullptr, list has odd numbers\r\n    if (fast) slow = slow->next;\r\n    slow = reverse(slow);    \r\n    while (slow) {\r\n      if (slow->val != head->val) return false;\r\n      slow = slow->next;\r\n      head = head->next;\r\n    }\r\n    return true;\r\n  }\r\nprivate:\r\n  ListNode* reverse(ListNode* head) {\r\n    ListNode* prev = nullptr;\r\n    ListNode* next = nullptr;\r\n    while (head) {\r\n      next = head->next;\r\n      head->next = prev;\r\n      prev = head;\r\n      head = next;\r\n    }\r\n    return prev;\r\n  }\r\n};<\/pre>\n
     <\/p>\n
     <\/p>\n
     <\/p>\n","protected":false},"excerpt":{"rendered":"
    \u9898\u76ee\u5927\u610f\uff1a\u68c0\u67e5\u4e00\u4e2a\u5355\u5411\u94fe\u8868\u662f\u4e0d\u662f\u56de\u6587\u3002 Problem: https:\/\/leetcode.com\/problems\/palindrome-linked-list\/description\/ Given a singly linked list, determine if it is a palindrome. Follow up: Could you do it in O(n) time and O(1)…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[50],"tags":[222,83,95],"class_list":["post-2081","post","type-post","status-publish","format-standard","hentry","category-list","tag-easy","tag-list","tag-palindrome","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2081","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=2081"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2081\/revisions"}],"predecessor-version":[{"id":2083,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2081\/revisions\/2083"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=2081"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=2081"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=2081"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}