回文链表

方法一：将值复制到数组中后用双指针法

思路

算法

#include<iostream>
using namespace std;
#include<vector>
  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 
 {
  public:
      bool isPalindrome(ListNode* head) 
      {
          vector<int> v;
          while (head)
          {
              //尾插元素
              v.emplace_back(head->val);
              head = head->next;
          }
          for (int i = 0, j = v.size() - 1; i < j; i++, j--)
          {
              if (v[i] != v[j])
                  return false;
          }
          return true;
      }
  };
//测试-----------------
void input(ListNode* l)
{
    int num;
    cin >> num;
    if (num == -1)
        return;
    l->val = num;
    ListNode* end = l;
    while (1)
    {
        cin >> num;
        if (num == -1)
            return;
        ListNode* newNode = new ListNode(num);
        end->next=newNode;
        end = newNode;
    }
}
void display(ListNode* l)
{
    if (l == NULL)
    {
        return;
    }
    while (l!=NULL)
    {
        cout << l->val;
        l = l->next;
    }
}
void test()
{
    ListNode* l = new ListNode(0);
    input(l);
    Solution s;
    bool ret=s.isPalindrome(l);
    cout << "链表打印：" << endl;
    display(l);
    cout << endl;
    if (ret)
    {
        cout << "是回文链表" << endl;
    }
    else {
        cout << "不是回文链表" << endl;
    }
}
int main()
{
    test();
    system("pause");
    return 0;
}

方法二：递归

使用递归反向迭代节点，同时使用递归函数外的变量向前迭代

 class Solution 
 {
     ListNode* frontPointer;
  public:
      //该函数用来对链表进行递归和回溯比较的操作
      bool  recursivelyCheck(ListNode* head)
      {
          //外层循环两个作用：
          //1.判断有没有遍历到尾节点
          //2.判断进行回溯的时候，比较有没有结束
          if (head!=NULL)
          {
              //这条If语句的作用：
              //1.不断进行递归，进行递归的过程中还没有进行判断
              //2.回溯阶段：
              //(1):遍历到尾节点的时候,不满嘴最外层if的head!=NULL,返回true，此时回退到尾节点
              //(2):从尾节点进行回退的过程中，如果出现不匹配，就表示该链表不是回文链表，便会一直满足该if语句条件，返回false，直到回溯结束，最后依然返回false
              //如果没出现不匹配的现象，那么因为函数返回值是true,不满足条件就一直不会执行该if语句里面的代码
              if (!recursivelyCheck(head->next))//通过递归找到尾节点
              {
                  return false;
              }
              //出现不匹配现象，就返回false
              if (head->val != frontPointer->val)
              {
                  return false;
              }
              //如果一直满足回文链表的条件，那么frontPointer就一直前移
              frontPointer = frontPointer->next;
         }
          //当回到最初状态的时候，当执行完上面if语句里面的代码后，就返回true
          return true;
      }
      bool isPalindrome(ListNode* head) 
      {
          frontPointer = head;
         return recursivelyCheck(head);
      }
  };