LeetCode 回文链表

今天药忘吃喽~ 2023-06-04 14:52 4阅读 0赞

题目链接：[https://leetcode-cn.com/problems/palindrome-linked-list/][https_leetcode-cn.com_problems_palindrome-linked-list]

### 题目大意 ###

略。

### 分析 ###

反转后半条链表，再判断可实现空间复杂度 O(1)。

### 代码如下 ###

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

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         ListNode *p1, *p2;
    13         int len = getLen(head);
    14         
    15         p1 = head;
    16         for(int i = 1; i <= (len - 1) >> 1; ++i) p1 = p1->next;
    17         p2 = reverseList(p1);
    18         p1 = head;
    19         
    20         while(p1 != NULL && p2 != NULL) {
    21             if(p1->val != p2->val) return false;
    22             p1 = p1->next;
    23             p2 = p2->next;
    24         }
    25         return true;
    26     }
    27     
    28     ListNode* reverseList(ListNode* head) {
    29         if(head == NULL || head->next == NULL) return head;
    30         
    31         ListNode *p1, *p2;
    32         p1 = head;
    33         p2 = head->next;
    34         p1->next = NULL;
    35         
    36         while(p2 != NULL) {
    37             ListNode *tmp = p2->next;
    38             
    39             p2->next = p1;
    40             p1 = p2;
    41             p2 = tmp;
    42         }
    43         
    44         return p1;
    45     }
    46     
    47     int getLen(ListNode* x) {
    48         int ret = 0;
    49         while(x != NULL) {
    50             ++ret;
    51             x = x->next;
    52         }
    53         return ret;
    54     }
    55 };

转载于:https://www.cnblogs.com/zaq19970105/p/11347658.html

[https_leetcode-cn.com_problems_palindrome-linked-list]: https://leetcode-cn.com/problems/palindrome-linked-list/
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/7132355d2f4448cb9633ac2f956a7661.png