leetcode 234. 回文链表

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

示例 1:

输入: 1->2
输出: false

示例 2:

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

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

解法1：遍历链表，分别放入栈中，然后出栈和链表从头遍历进行比较，如果不等为false，最后能够结束为true，时间复杂度为O(n),空间复杂度为O(n)

/**
 * 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) {
        stack<ListNode *> stk;
        ListNode *p=head;;
        while(p)
        {
            stk.push(p);
            p=p->next;
        }
        while(head)
        {
            if(stk.top()->val!=head->val)
                return false;
            stk.pop();
            head=head->next;
        }
        return true;
    }
};

 

解法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==nullptr||head->next==nullptr)
            return true;
        ListNode *fast=head;
        ListNode *low=head;
        stack<ListNode*>stk;
        while(fast)
        {
            if(fast->next==nullptr)
            {
                break;
            }
            else
            {
                fast=fast->next->next;
                low=low->next;
            }
        }
        while(low)
        {
            stk.push(low);
            low=low->next;
        }
        
        while(!stk.empty())
        {
            if(stk.top()->val!=head->val)
                return false;
            head=head->next;
            stk.pop();
        }
        return true;
    }
};

这里要说明一下，当fast本身为空，或者next为空都要停止，看图

这种解法省了一半空间，因为算复杂度常数项要省略，所以空间还是O(n),时间还是O(n)

 

解法3：和解法二一样，走到low走到中点时，将low到尾部的这一串进行链表反转，然后再从头和这反转的链表比较

/**
 * 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==nullptr||head->next==nullptr)
            return true;
        ListNode *fast=head;
        ListNode *low=head;
        stack<ListNode*>stk;
        while(fast) //到了最后一个位置的下一个位置就是nullptr也停 双数情况 1001  最后到了nullptr
        {
            if(fast->next==nullptr)   //如果fast到最后一个位置了就停 单数情况比如 101 最后到了 1
            {
                break;
            }
            else
            {
                fast=fast->next->next;
                low=low->next;
            }
        }
        
        //反转low到结尾的那一段链表
        ListNode *pre=nullptr;
        while(low)  
        {
            ListNode *temp=low->next;
            low->next=pre;
            pre=low;
            low=temp;
        }
        
        //从头开始比较反转low到结尾的那一段链表
        while(pre)
        {
            if(pre->val!=head->val)
                return false;
            head=head->next;
            pre=pre->next;
            
        }
        return true;
    }
};

解法三的空间复杂度为O(1),时间复杂度为O(n),满足题目要求，其中反转的那一部分详细可以参照 leetcode 206 反转链表