大家好，又见面了，我是全栈君。
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);
}
};版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/115288.html原文链接：https://javaforall.net
