广东广州自己建网站公司,wordpress 足球,网站建设方案汇报,达人室内设计网app文章目录 一、题目二、C# 题解 一、题目 编写一个函数#xff0c;检查输入的链表是否是回文的。 点击此处跳转题目。
示例 1#xff1a; 输入#xff1a; 1-2 输出#xff1a; false 示例 2#xff1a; 输入#xff1a; 1-2-2-1 输出#xff1a; true … 文章目录 一、题目二、C# 题解 一、题目 编写一个函数检查输入的链表是否是回文的。 点击此处跳转题目。
示例 1 输入 1-2 输出 false 示例 2 输入 1-2-2-1 输出 true 进阶
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题
二、C# 题解 使用 O ( n ) O(n) O(n) 空间很容易写出来只需要开辟一个数组或者反向链表即可。这里为了实现进阶要求在原链表上修改。首先将链表的前半部分翻转然后比较前后两个链表是否相同最后恢复原链表即可具体实现细节见代码注释
/*** Definition for singly-linked list.* public class ListNode {* public int val;* public ListNode next;* public ListNode(int x) { val x; }* }*/
public class Solution {public bool IsPalindrome(ListNode head) {int n 0, i;ListNode p head, q;bool result;// 统计链表长度while (p ! null) {p p.next;n;}if (n 1) return true; // 长度 1一定是回文串i n / 2; // 长度的一半向下取整p head;while (--i 0) p p.next; // 定位到链表中间q p.next;p.next null; // 断开链表Reverse(head); // 翻转前半部分// 判断链表前后两部分是否相同if (n % 2 0) result Same(p, q);else result Same(p, q.next); // 奇数长度的链表需要跳过最中间的元素// 恢复链表原状Reverse(p);p.next q;return result;}// 翻转链表public ListNode Reverse(ListNode head) {ListNode p null, q head, r;while (q ! null) {r q.next;q.next p;p q;q r;}return p;}// 比较两个链表是否相同public bool Same(ListNode h1, ListNode h2) {while (h1 ! null h2 ! null) {if (h1.val ! h2.val) return false;h1 h1.next;h2 h2.next;}return h1 null h2 null;}
}时间复杂度 O ( n ) O(n) O(n)。空间复杂度 O ( 1 ) O(1) O(1)。 看了一下官方解法发现还可以进行优化。使用快慢指针定位到中间节点代码会更加高级和优雅hh。但是效率和上面统计长度然后遍历一半进行定位的方式差不多因为都是遍历了一个半链表快指针遍历整个链表慢指针遍历半个链表但是快慢指针这种方法它显得高级呀哈哈
/*** Definition for singly-linked list.* public class ListNode {* public int val;* public ListNode next;* public ListNode(int x) { val x; }* }*/
public class Solution {public bool IsPalindrome(ListNode head) {if (head null || head.next null) return true;ListNode p head, q p.next; // p慢指针q快指针bool result;while (q ! null q.next ! null) {q q.next.next; // q 前进两格if (q ! null) p p.next; // q 不为空p 才前进}ListNode r p.next; // 定位到后半段链表的首部p.next null; // 断开链表Reverse(head); // 翻转前半部分// 判断链表前后两部分是否相同if (q ! null) result Same(p, r);else result Same(p, r.next); // 奇数长度的链表需要跳过最中间的元素// 恢复链表原状Reverse(p);p.next r;return result;}// 翻转链表public ListNode Reverse(ListNode head) {ListNode p null, q head, r;while (q ! null) {r q.next;q.next p;p q;q r;}return p;}// 比较两个链表是否相同public bool Same(ListNode h1, ListNode h2) {while (h1 ! null h2 ! null) {if (h1.val ! h2.val) return false;h1 h1.next;h2 h2.next;}return h1 null h2 null;}
}时间复杂度 O ( n ) O(n) O(n)。空间复杂度 O ( 1 ) O(1) O(1)。 修改过后发现快慢指针跑出来的速度不如直接统计链表长度来得快。果然高端的代码往往以最朴素的方法写出来~
