234. 回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

解题思路

• 遍历获取链表长度，同时计算得到中间节点；
• 然后再次遍历链表，将中间节点之前的节点值存入数组中；
• 对于中间节点之后的节点，判断其值是否与数组中对应项的值相等；
• 需要注意的是，当总数为奇数个节点时，中间节点需要直接跳过。

/**
 * 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
{
public:
  bool isPalindrome(ListNode *head)
  {
    int len = 1;
    ListNode *cur = head;

    while (cur->next)
    {
      len++;
      cur = cur->next;
    }
    if (len == 1)
    {
      return true;
    }
    bool is_ood = false;
    if (len % 2 != 0)
    {
      is_ood = true;
    }

    ListNode *left = head;
    ListNode *right = head;
    int total = len;
    len = len / 2;
    int i = 1;
    int nums[len];

    while (i <= total)
    {
      // 奇数个节点时，中间节点需要直接跳过
      if (is_ood && i == len + 1)
      {
        i++;
        right = right->next;
        continue;
      }

      if (i <= len)
      {
        nums[i - 1] = right->val;
      }

      if ((!is_ood && i > len) || (is_ood && i > len + 1))
      {
        if (nums[total - i] != right->val)
        {
          return false;
        }
      }

      i++;
      right = right->next;
    }

    return true;
  }
};

参考

• 234. 回文链表 - 力扣（LeetCode） (opens new window)