234 回文链表

请判断一个链表是否为回文链表。

示例 1:

输入: 1->2
输出: false

示例 2:

输入: 1->2->2->1
输出: true

进阶： 你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

解法

• Python (借用栈空间)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        cur = head
        stack = []
        while cur:
            stack.append(cur.val)
            cur = cur.next
        while stack and head:
            if stack.pop()!=head.val:
                return False
            else:
                head = head.next
        return True

• C++(借助栈空间)

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        stack<int> s;
        ListNode *p = head;
        while(p){
            s.push(p->val);
            p = p->next;
        }
        p = head;
        while(p){
            if(p->val != s.top()){
                return false;
            }
            s.pop();
            p = p->next;
        }
        return true;
    }
};

• C++，快慢指针法

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if (head == NULL ||head->next==NULL){
            return true;
        }
        ListNode* pre = NULL;
        ListNode* slow = head, * fast = head;

        while (fast!=NULL&&fast->next!=NULL){
            // pre = slow;
            fast = fast->next->next;
            ListNode* tmp =  slow->next;
            slow->next = pre;
            pre = slow;
            slow =  tmp;
        }
        if (fast){
            slow = slow->next;
        }
        while (pre!=NULL){
            if(pre->val != slow->val){
                return false;
            }
            pre = pre->next;
            slow = slow->next;
        }
        return true;
    }
};