leetcode 234 回文链表 Palindrome Linked List

浅浅的花香味﹌ 2021-12-21 01:17 198阅读 0赞

![1588437-20190227214511956-2063467543.png][]

要求用O(n)时间，和O(1)空间，因此思路是用本身链表进行判断，既然考虑回文，本方法思想是先遍历一次求链表长度，然后翻转前半部分链表；然后同时对前半部分链表和后半部分链表遍历，来判断对应节点的值是否对应相等，时间复杂度应该为O(2n),空间复杂度O(3)；基本符合要求，但是运行时间还是有点长；

1 /**
     2  * Definition for singly-linked list.
     3  * struct ListNode {
     4  *     int val;
     5  *     ListNode *next;
     6  *     ListNode(int x) : val(x), next(NULL) {}
     7  * };
     8  */
     9 class Solution {
    10 public:
    11     bool isPalindrome(ListNode* head) {
    12         if(head==NULL||head->next==NULL) return true;
    13         ListNode* cur,*pre;
    14         cur=head;
    15         int length=0;
    16         while(cur!=NULL){
    17             length+=1;
    18             cur=cur->next;
    19         }
    20         cur=head->next;pre=head;head->next=NULL;
    21         for(int i=1;i<(length+1)/2;i++){
    22                 ListNode* temp;
    23                 temp=cur->next;
    24                 cur->next=pre;
    25                 pre=cur;
    26                 cur=temp;
    27         }
    28         if(length%2==1) pre=pre->next;
    29         while(cur!=NULL){
    30             if(cur->val==pre->val){
    31                 cur=cur->next;pre=pre->next;
    32             }
    33             else return false;
    34         }
    35         return true;
    36     }
    37 };

![1588437-20190227215028275-1897613848.png][]

转载于:https://www.cnblogs.com/joelwang/p/10447280.html

[1588437-20190227214511956-2063467543.png]: /images/20211221/056644f483194d3abce10b3d26b207f9.png
[1588437-20190227215028275-1897613848.png]: /images/20211221/6cb0d8e00f634b18a3f1fb933f4aa0c4.png