文章目录

• 一【题目类别】
• 二【题目难度】
• 三【题目编号】
• 四【题目描述】
• 五【题目示例】
• 六【题目提示】
• 七【题目进阶】
• 八【解题思路】
• 九【时间频度】
• 十【代码实现】
• 十一【提交结果】

一【题目类别】

• 链表

二【题目难度】

• 简单

三【题目编号】

• 234.回文链表

四【题目描述】

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

五【题目示例】

• 示例 1：
  
  输入：head = [1,2,2,1]
  输出：true

• 示例 2：
  
  输入：head = [1,2]
  输出：false

六【题目提示】

• 链表中节点数目在范围[ 1 , 105 ] [1, 10^5] [1,105]内
• 0 <= Node.val <= 9

七【题目进阶】

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

八【解题思路】

• 如果用栈或者数组做这个题很简单，没有什么难度，但是题目进阶说了要保证$O(1)$的时间复杂度，也就是说不能开辟新的内存空间。那么我们可以利用快慢指针的思想来保证题目要求的时间复杂度。具体思路如下：
  ①：首先用快慢指针找到链表中点
  ②：然后将链表后半段反转
  ③：最后逐一对比两个链表即可，如果有不同的就不是回文链表，否则就是回文链表

九【时间频度】

• 时间复杂度：$O(n)$，其中$n$为链表长度
• 空间复杂度：$O(1)$

十【代码实现】

1. Java语言版

package LinkedList;public class p234_PalindromicLinkedList {    int val;    p234_PalindromicLinkedList next;    public p234_PalindromicLinkedList() {    }    public p234_PalindromicLinkedList(int val) { this.val = val;    }    public p234_PalindromicLinkedList(int val, p234_PalindromicLinkedList next) { this.val = val; this.next = next;    }    public static void main(String[] args) { p234_PalindromicLinkedList node1 = new p234_PalindromicLinkedList(1); p234_PalindromicLinkedList node2 = new p234_PalindromicLinkedList(2); p234_PalindromicLinkedList node3 = new p234_PalindromicLinkedList(2); p234_PalindromicLinkedList node4 = new p234_PalindromicLinkedList(1); node1.next = node2; node2.next = node3; node3.next = node4; boolean res = isPalindrome(node1); System.out.println(res);    }    public static boolean isPalindrome(p234_PalindromicLinkedList head) { p234_PalindromicLinkedList slow = head, fast = head, pre = null, temp = null; while (fast != null) {     slow = slow.next;     fast = fast.next != null ? fast.next.next : fast.next; } while (slow != null) {     temp = slow.next;     slow.next = pre;     pre = slow;     slow = temp; } while (head != null && pre != null) {     if (head.val != pre.val) {  return false;     }     head = head.next;     pre = pre.next; } return true;    }}

2. C语言版

#include#includestruct ListNode{int val;struct ListNode *next;};bool p234_PalindromicLinkedList_isPalindrome(struct ListNode* head){struct ListNode *slow = head, *fast = head, *pre = NULL, *temp = NULL;while (fast != NULL){slow = slow->next;fast = fast->next ? fast->next->next : fast->next;}while (slow != NULL){temp = slow->next;slow->next = pre;pre = slow;slow = temp;}while (head != NULL && pre != NULL){if (head->val != pre->val){return false;}head = head->next;pre = pre->next;}return true;}/*主函数省略*/

十一【提交结果】

1. Java语言版
   

2. C语言版
   

创作打卡挑战赛 赢取流量/现金/CSDN周边激励大奖