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
      
        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);    }};