力扣刷题15--回文链表

分手后的思念是犯贱 2023-02-28 11:10 15阅读 0赞

晚上时间不够刷一个简单的练练手，跳过14题后面补上，奥里给！！！

**题目**

**编写一个函数，检查输入的链表是否是回文的。**

示例 1：
    
    输入： 1->2
    输出： false 
    示例 2：
    
    输入： 1->2->2->1
    输出： true

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

[力扣出处面试金典][Link 1]

**解析**

详见代码，一目了然，利用`vector`数组进行旋转，比较是否相等即可。

**代码**

/** * 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) { 
            ListNode* current = head;
            std::vector<int> vec1;
            std::vector<int> vec2;
            while(current)
            { 
                vec1.push_back(current->val);
                current = current->next;
            }
            vec2 = vec1;
            reverse(vec1.begin(),vec1.end());  //反转
            return vec1 == vec2;
        }
    };
    //hmtian @2020/7/20

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM3ODgwMA_size_16_color_FFFFFF_t_70]

**快慢指针解法**

个人觉得代码没我的简单…  
[\----------》出处][----------]

/** * 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*slow=head;
           ListNode*pre=NULL;
           while(fast&&fast->next){ 
               slow=slow->next;
               fast=fast->next->next;
           }
           while(slow){ 
               ListNode*tmp=slow->next;
               slow->next=pre;
               pre=slow;
               slow=tmp;
           }
           while(head&&pre){ 
               if(head->val!=pre->val){ 
                   return false;
               }
               head=head->next;
               pre=pre->next;
           }
           return true;
        }
    };

[Link 1]: https://leetcode-cn.com/problems/zero-matrix-lcci
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM3ODgwMA_size_16_color_FFFFFF_t_70]: /images/20230209/1e2b80e94833443d8f849f815d2c3790.png
[----------]: https://leetcode-cn.com/problems/palindrome-linked-list-lcci/solution/c-kuai-man-zhi-zhen-fan-zhuan-hou-ban-bu-fen-lian-/