leetcode 234. Palindrome Linked List 回文链表的判断 + 双指针

短命女 2022-06-08 12:15 128阅读 0赞

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?

建议和[leetcode 680. Valid Palindrome II 去除一个字符的回文字符串判断 + 双指针][leetcode 680. Valid Palindrome II _ _] 一起学习

反转链表判断即可。

代码如下：

/*class ListNode 
    {
          int val;
          ListNode next;
          ListNode(int x) { val = x; }
    }*/
    
    /*
     * 回文链表的判断
     * 这个问题的关键是O（1）的内存
     * 其实可以使用快慢指针分割链表
     * 可以使用栈判断，但是内存使用多了
     * 所以反转链表即可
     * */
    public class Solution 
    {
        public boolean isPalindrome(ListNode head) 
        {
            if(head==null || head.next==null)
                return true;
    
            ListNode slow=head,fast=head;
            while(fast!=null && fast.next!=null)
            {
                slow=slow.next;
                fast=fast.next.next;
            }       
            //奇数个元素
            if(fast!=null)
                slow=slow.next;
            slow=reverList(slow);
            //回文判断
            while(slow!=null)
            {
                if(head.val!=slow.val)
                    return false;
                head=head.next;
                slow=slow.next;
            }
            return true;
        }
        /*
         * 反转链表需要好好记一下，
         * 反思一下
         * */
        ListNode reverList(ListNode head)
        {
            ListNode pre=null;
            while(head!=null)
            {
                ListNode next=head.next;
                head.next=pre;
                pre=head;
                head=next;
            }
            return pre;
        }
    }

下面是C++的做法，本题的题意就是使用双指针来分割链表，然后反转链表来判断回文链表

代码如下：

#include <iostream>
    #include <algorithm>
    #include <vector>
    #include <set>
    #include <string>
    #include <map>
    
    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 == NULL || head->next==NULL)
                return true;
            vector<int> one;
            ListNode* i = head;
            while (i != NULL)
            {
                one.push_back(i->val);
                i = i->next;
            }
    
            int j = 0, k = one.size() - 1;
            while (j < k)
            {
                if (one[j] != one[k])
                    return false;
                else
                {
                    j++;
                    k--;
                }
            }
            return true;
        }
    };

[leetcode 680. Valid Palindrome II _ _]: http://blog.csdn.net/jackzhang_123/article/details/78880022