C++刷LeetCode（面试题 02.06. 回文链表）【翻转链表】

糖逗

题目描述：

1. 编写一个函数，检查输入的链表是否是回文的。
   
2. 
   
3.  
   
4. 
   
5. 示例 1：
   
6. 
   
7. 输入： 1->2
   
8. 输出： false
   
9. 示例 2：
   
10. 
    
11. 输入： 1->2->2->1
    
12. 输出： true
    
13.  
    
14. 
    
15. 进阶：
    
16. 你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
    
17. 
    
18. 来源：力扣（LeetCode）
    
19. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

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.         //计算链表长度
    
14.         int count = 0;
    
15.         ListNode*temp1 = head;
    
16.         while(temp1){
    
17.             temp1 = temp1 -> next;
    
18.             count++;
    
19.         }
    
20.         //翻转前半截链表
    
21.         ListNode*temp2 = head;//注意此处！！！
    
22.         temp1 = NULL;//注意此处！！！
    
23.         int len = 1;
    
24.         while(len <= count / 2){
    
25.             ListNode*temp = temp2 -> next;
    
26.             temp2 -> next = temp1;
    
27.             temp1 = temp2;
    
28.             temp2 = temp;
    
29.             len++;
    
30.         }
    
31.         //比较前后两段
    
32.         if(count % 2 == 1)temp2 = temp2 -> next;
    
33.         while(temp2){
    
34.             if(temp1->val != temp2->val)return false;
    
35.             temp1 = temp1->next;
    
36.             temp2 = temp2->next;
    
37.         }
    
38.         return true;
    
39.     }
    
40. };

复制代码