leetcode 链接：234. 回文链表

题目

请判断一个链表是否为回文链表。

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

示例：

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

解答 & 代码

  • 先用快慢指针找到链表中点，将链表拆成两部分，左右两部分节点数相同，或者左边节点数多一个
  • 将右半部分链表翻转
  • 双指针依次比较左半部分链表和翻转后的右半部分链表节点，如果遇到值不一样的就返回 false

  • 遍历结束，将链表右半部分重新逆序，并将左半边和右半边重新连接，返回 true

    /**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode() : val(0), next(nullptr) {}
*     ListNode(int x) : val(x), next(nullptr) {}
*     ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
private:
  // 寻找链表左半边的尾节点
  // 如果链表 4 个节点，则为第 2 个节点；如果链表 5 个节点，则为第 3 个节点
  ListNode* findEndOfLeft(ListNode* head)
  {
      if(head == nullptr)
          return nullptr;

      ListNode* slow = head;
      ListNode* fast = head->next;
      while(fast != nullptr && fast->next != nullptr)
      {
          slow = slow->next;
          fast = fast->next->next;
      }
      return slow;
  }

  // 翻转链表
  ListNode* reverseList(ListNode* head)
  {
      ListNode* pre = nullptr;
      ListNode* cur = head;
      while(cur != nullptr)
      {
          ListNode* next = cur->next;
          cur->next = pre;
          pre = cur;
          cur = next;
      }
      return pre;
  }
public:
  bool isPalindrome(ListNode* head) {
      if(head == nullptr || head->next == nullptr)
          return true;

      // 1、找到链表左半部分的尾节点
      ListNode* leftEnd = findEndOfLeft(head);

      // 2、将右半部分链表逆转
      ListNode* rightHead = leftEnd->next;
      rightHead = reverseList(rightHead);

      // 3、双指针遍历左、右两个链表系欸但
      ListNode* cur1 = head;
      ListNode* cur2 = rightHead;
      while(cur2 != nullptr)
      {
          if(cur1->val != cur2->val)    // 如果遇到两个节点的值不同，直接返回 false
              return false;
          cur1 = cur1->next;
          cur2 = cur2->next;
      }

      // 4、将链表右半部分重新逆序，并和左半边连接
      leftEnd->next = reverseList(rightHead);
      return true;
  }
};

    执行结果： ``` 执行结果：通过

执行用时：176 ms, 在所有 C++ 提交中击败了 93.20% 的用户 内存消耗：112.2 MB, 在所有 C++ 提交中击败了 63.89% 的用户 ```