请判断一个链表是否为 回文链表 ：其实就是链表反转之后和之前一样，比如：

  1. 示例1
  2. 输入:1->2
  3. 输出:false
  5. 示例2：
  6. 输入:1->2->2->1
  7. 输出:true

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

复制到数组->双指针

  1. 复制链表值到数组中
  2. 使用双指针判断是否为回文（一个指针指向数组头，一个指针指向数组尾，同时往中间走，当碰面的时候如果一直相同咋是回文） ```c /**
    • Definition for singly-linked list.
    • struct ListNode {
    • int val;
    • struct ListNode *next;
    • }; */

bool isPalindrome(struct ListNode* head){ int array[50001]; int index = 0; while (head) { array[index] = head->val; head = head->next; index++; }

  1. for (int left = 0,right = index-1;left < right;left++,right--) {
  2.     if (array[left] != array[right]) {
  3.         return false;
  4.     }
  5. }
  6. return true;

}

  2. - 时间复杂度：
  3.    - 第一步：遍历链表 `O(n)` ,
  4.    - 第二步：双指针又遍历数组 `O(n/2)` 也是 `O(n)` ，总的时间复杂度是 `O(2n)=O(n)` 
  5. - 空间复杂度： `O(n)` ，其中n表示链表的元素个数，我们使用了一个数组来存放链表的元素值。
  7. <a name="f7zY7"></a>
  8. ## 递归
  10. 1. 创建一个外部变量 `previousNode` 来保存链表的头节点
  11. 1. `currentNode` 进行迭代直到找到尾节点
  12. 1. 当找到尾节点的时候再开始反向遍历进行比较：
  13.    1. 如果值相等返回true表示当前头尾节点相同，然后头节点指向 `next` 的同时 `currentNode`  也会前移（递归栈思想）
  14.    1. 如果值不相等直接返回false
  15. ```c
  16. /**
  17.  * Definition for singly-linked list.
  18.  * struct ListNode {
  19.  *     int val;
  20.  *     struct ListNode *next;
  21.  * };
  22.  */
  24. struct ListNode *previousNode;
  26. bool recursionNode(struct ListNode *currentNode) {
  27.     if  (currentNode != NULL) {
  28.         if (!recursionNode(currentNode->next)) {
  29.             return false;
  30.         }
  31.         if (currentNode->val != previousNode->val) {
  32.             return false;
  33.         }
  35.         previousNode = previousNode->next;
  36.     }
  37.     return true;
  38. }
  40. bool isPalindrome(struct ListNode* head){
  41.     previousNode = head;
  42.     return recursionNode(head);
  43. }

时间复杂度： O(n)
空间复杂度： O(n)

快慢指针

  1. 找到前半部分链表的尾节点
  2. 反转后半部分链表
  3. 依次对比两个链表的节点值，判断是否回文
  4. 恢复链表
  5. 返回结果 ```c /**
    • Definition for singly-linked list.
    • struct ListNode {
    • int val;
    • struct ListNode *next;
    • }; / // 反转链表 struct ListNode reverseNode(struct ListNode head) { struct ListNode currentNode = head; struct ListNode preNode = NULL; while (currentNode) { struct ListNode temp = currentNode->next; currentNode->next = preNode; preNode = currentNode; currentNode = temp; } return preNode; }

// 快慢指针（快指针一次走两步，慢指针一次走一步，当快指针到链表尾部慢指针正好到链表中间） struct ListNode halfEndNode(struct ListNode head) { struct ListNode fast = head; struct ListNode slow = head; while (fast->next != NULL && fast->next->next != NULL) { slow = slow->next; fast = fast->next->next; } return slow; }

bool isPalindrome(struct ListNode head){ if (head == NULL) { return true; } // 找到前半部分链表的尾结点并反转后半部分链表 struct ListNode firstHalfEnd = halfEndNode(head); struct ListNode endHalfReverse = reverseNode(firstHalfEnd->next); // 判断回文 struct ListNode temp1 = head; struct ListNode *temp2 = endHalfReverse; bool result = true; while (result && temp2) { if (temp1->val != temp2->val) { result = false; } temp1 = temp1->next; temp2 = temp2->next; }

  1. // 还原链表
  2. firstHalfEnd->next = reverseNode(endHalfReverse);
  3. return result;

} ```

  • 时间复杂度： O(n) 其中 n 指的是链表的大小
  • 空间复杂度: O(1) 我们只会修改原本链表中节点的指向，而在堆栈上的堆栈帧不超过 O(1)