糖逗 发表于 2020-7-11 14:42:07

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

本帖最后由 糖逗 于 2020-7-13 09:43 编辑

题目描述:
编写一个函数,检查输入的链表是否是回文的。

 

示例 1:

输入: 1->2
输出: false
示例 2:

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

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

来源:力扣(LeetCode)
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


/**
* 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 == NULL || head -> next == NULL)return true;
      //计算链表长度
      int count = 0;
      ListNode*temp1 = head;
      while(temp1){
            temp1 = temp1 -> next;
            count++;
      }
      //翻转前半截链表
      ListNode*temp2 = head;//注意此处!!!
      temp1 = NULL;//注意此处!!!
      int len = 1;
      while(len <= count / 2){
            ListNode*temp = temp2 -> next;
            temp2 -> next = temp1;
            temp1 = temp2;
            temp2 = temp;
            len++;
      }
      //比较前后两段
      if(count % 2 == 1)temp2 = temp2 -> next;
      while(temp2){
            if(temp1->val != temp2->val)return false;
            temp1 = temp1->next;
            temp2 = temp2->next;
      }
      return true;
    }
};
页: [1]
查看完整版本: C++刷LeetCode(面试题 02.06. 回文链表)【翻转链表】