LeetCode——234回文链表

问题描述：

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

示例 1:
输入: 1->2
输出: false

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

执行结果：

代码描述：

借助快慢指针，和栈，进行判断。

快指针走两步，慢指针走一步，同时把慢指针的数字放入stack中。

当快指针都到尾，慢指针走到中间（注意奇偶），

慢指针继续往后走，同时，对比栈顶的元素，栈顶弹栈。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution{
public:
    bool isPalindrome(ListNode* pHead) {
        if(pHead == NULL)
            return true;
        stack<int> ss;
        ListNode* p = pHead;
        ListNode* q = pHead;
        ss.push(p->val);
        while(q->next != NULL && q->next->next != NULL)
        {
            p = p->next;
            ss.push(p->val);
            q = q->next->next;
        }
        if(q->next == NULL)                                                    //长度为奇数
            ss.pop();
        p = p->next;
        while(!ss.empty())
        {
            if(ss.top() != p->val)
                break;
            p = p->next;
            ss.pop();
        }
        if(ss.empty())
            return true;
        else
            return false;
    }
};
           

把原链改了，快慢指针，慢指针边走，边反转前半段，然后再对比。就可以实现O(n)的时间复杂度，O(1)的空间复杂度。——摘自Michael阿明

class Solution {//leetcode 234
public:
    bool isPalindrome(ListNode* head) {
        if(!head || !head->next)
        	return true;
        ListNode *fast = head, *slow = head, *prev = NULL, *nextNode = NULL;
        while(fast && fast->next)
        {
        	fast = fast->next->next;
        	nextNode = slow->next;
        	slow->next = prev;
        	prev = slow;
        	slow = nextNode;
        }
        if(fast != NULL)//奇数个节点情况
        	slow = slow->next;
        while(slow)
        {
        	if(prev->val != slow->val)
        		return false;
        	prev = prev->next;
        	slow = slow->next;
        }
        return true;
    }
};