题目链接

题目描述

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

示例

示例1：

输入: 1->2 输出: false

思路

思路1：数组+双指针

将链表的值存到数组中，使用双指针判断是否是回文。

思路2：迭代

使用快慢指针将链表平分，将后半部分反转，再判断是否是回文。
注：最好不要修改原链表的结构，若修改，再返回前再修改回来。

题解

思路1：数组+双指针

  1. /**
  2.  * Definition for singly-linked list.
  3.  * struct ListNode {
  4.  *     int val;
  5.  *     ListNode *next;
  6.  *     ListNode() : val(0), next(nullptr) {}
  7.  *     ListNode(int x) : val(x), next(nullptr) {}
  8.  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
  9.  * };
  10.  */
  11. class Solution {
  12.    public:
  13.     bool isPalindrome(ListNode* head) {
  14.         vector<int> vec;
  15.         while (head) {
  16.             vec.emplace_back(head->val);
  17.             head = head->next;
  18.         }
  19.         int left = 0, right = vec.size() - 1;
  20.         while (left < right) {
  21.             if (vec[left] != vec[right]) {
  22.                 return false;
  23.             }
  24.             ++left;
  25.             --right;
  26.         }
  27.         return true;
  28.     }
  29. };

思路2：迭代

  1. /**
  2.  * Definition for singly-linked list.
  3.  * struct ListNode {
  4.  *     int val;
  5.  *     ListNode *next;
  6.  *     ListNode() : val(0), next(nullptr) {}
  7.  *     ListNode(int x) : val(x), next(nullptr) {}
  8.  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
  9.  * };
  10.  */
  11. class Solution {
  12.    private:
  13.     ListNode* splitList(ListNode* head) {
  14.         ListNode* fast = head;
  15.         ListNode* slow = head;
  16.         while (fast->next != nullptr && fast->next->next != nullptr) {
  17.             fast = fast->next->next;
  18.             slow = slow->next;
  19.         }
  20.         return slow;
  21.     }
  23.     ListNode* reverseList(ListNode* head) {
  24.         ListNode* prev = nullptr;
  25.         ListNode* curr = head;
  26.         ListNode* next = nullptr;
  27.         while (curr) {
  28.             next = curr->next;
  29.             curr->next = prev;
  30.             prev = curr;
  31.             curr = next;
  32.         }
  34.         return prev;
  35.     }
  37.    public:
  38.     bool isPalindrome(ListNode* head) {
  39.         if (head == nullptr) {
  40.             return true;
  41.         }
  42.         ListNode* firstPartTail = splitList(head);
  43.         ListNode* secondPartHead = reverseList(firstPartTail->next);
  45.         ListNode* p1 = head;
  46.         ListNode* p2 = secondPartHead;
  47.         bool ret = true;
  48.         while (p2) {
  49.             if (p1->val != p2->val) {
  50.                 ret = false;
  51.                 break;
  52.             }
  53.             p1 = p1->next;
  54.             p2 = p2->next;
  55.         }
  57.         firstPartTail->next = reverseList(secondPartHead);
  58.         return ret;
  59.     }
  60. };

复杂度分析

思路1：数组+双指针

  • 时间复杂度：0234-回文链表 - 图1

  • 空间复杂度：0234-回文链表 - 图2

    思路2：迭代

  • 时间复杂度：0234-回文链表 - 图3

  • 空间复杂度：0234-回文链表 - 图4