Leetcode 234 Palindrome Linked List 复杂度为时间O(n) 和空间（1）解法[通俗易懂]

全栈程序员-用户IM • 2022年2月6日下午3:00 • 未分类

大家好，又见面了，我是全栈君。

1. 问题描写叙述

　　给定一个单链表，推断其内容是不是回文类型。

比如1–>2–>3–>2–>1。时间和空间复杂都尽量低。

2. 方法与思路

　　1）比較朴素的算法。

　　因为给定的数据结构是单链表，要訪问链表的尾部元素，必须从头開始遍历。为了方便推断。我们能够申请一个辅助栈结构来存储链表的内容，第一次遍历将链表节点值依次入栈，第二次遍历比較推断是否为回文。

/** * 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;
        stack<int> st;
    ListNode *tmp = head;
        while(tmp)
        {
            st.push(tmp->val);
            tmp = tmp->next;
        }

    while(head)
    {
        if(head->val != st.top() ) return false;
        head = head->next;
        st.pop();
    }
        return true;
    }
};

　　2). 时间O(n)和空间O(1)解法
　　既然用到了栈，能够想到递归的过程本身就是出入栈的过程，我们能够先递归訪问单链表，然后做比較。这样就省去了辅助空间，从而将空间复杂度降为O(1)。代码例如以下：
　　

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
class Solution {
private:
    ListNode *lst;
public:
    bool judge(ListNode *head)
    {
        if(head == NULL) return true;

        if(judge(head->next) == false) return false;

        if(lst->val != head->val) return false;
        else{
            lst = lst->next;
            return true;
        }
    }
    bool isPalindrome(ListNode* head) {
        if(head == NULL || head->next == NULL) return true;
        lst = head;

        return judge(head);
    }
};