秦皇岛网站建设服务宁远做网站msoer

秦皇岛网站建设服务,宁远做网站msoer,网站有了如何做推广,网页设计平均工资问题描述 给定一个单链表的头节点 head#xff0c;判断该链表是否为回文链表。如果是#xff0c;返回 true#xff1b;否则#xff0c;返回 false。 示例 #xff1a; 输入: head [1,2,2,1] 输出: true输入: head [1,2] 输出: false 进阶#xff1a; 你能否用 O(n)…问题描述给定一个单链表的头节点head判断该链表是否为回文链表。如果是返回true否则返回false。示例 输入: head [1,2,2,1] 输出: true输入: head [1,2] 输出: false进阶你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题解法一反转后半部分链表最优解这是面试中最常考的方法时间复杂度 O(n)空间复杂度 O(1)。算法步骤使用快慢指针找到链表的中间节点反转链表的后半部分比较前半部分和反转后的后半部分恢复链表可选代码实现class Solution { public boolean isPalindrome(ListNode head) { if(headnull||head.nextnull){ return true; } ListNode midFind_mid(head); ListNode head2reverse_List(mid); while(head2!null){ if(head.val!head2.val){ return false; } headhead.next; head2head2.next; } return true; } private ListNode reverse_List(ListNode head){//反转链表 ListNode prenull; ListNode curhead; while(cur!null){ ListNode Tempcur.next; cur.nextpre; precur; curTemp; } return pre; } private ListNode Find_mid(ListNode head){//找到中间节点 ListNode slowhead; ListNode fasthead; while(fast!nullfast.next ! null){ slowslow.next; fastfast.next.next; } return slow; } }关键点分析快慢指针找中点慢指针每次走一步快指针每次走两步当快指针到达末尾时慢指针正好在中点对于奇数长度链表慢指针停在中间节点对于偶数长度链表慢指针停在中间两个节点的第二个反转链表使用三个指针pre、curr、Tempcur指向prepre往前移cur往前移每次迭代将当前节点的next指向前一个节点时间复杂度与空间复杂度时间复杂度O(n)找中点O(n/2) ≈ O(n)反转后半部分O(n/2) ≈ O(n)比较两部分O(n/2) ≈ O(n)总时间O(n)空间复杂度O(1)只使用了常数级别的额外空间解法二使用栈思路利用栈的后进先出特性将链表元素入栈然后依次出栈与链表比较。代码实现javaclass Solution { public boolean isPalindrome(ListNode head) { if (head null || head.next null) { return true; } StackInteger stack new Stack(); ListNode current head; // 将链表值压入栈中 while (current ! null) { stack.push(current.val); current current.next; } // 比较栈顶元素和链表当前值 current head; while (current ! null) { if (current.val ! stack.pop()) { return false; } current current.next; } return true; } }复杂度分析时间复杂度O(n)需要遍历链表两次空间复杂度O(n)需要额外栈空间解法三递归思路利用递归的调用栈从链表末尾开始比较。代码实现javaclass Solution { private ListNode frontPointer; public boolean isPalindrome(ListNode head) { frontPointer head; return recursivelyCheck(head); } private boolean recursivelyCheck(ListNode currentNode) { if (currentNode ! null) { // 递归到链表末尾 if (!recursivelyCheck(currentNode.next)) { return false; } // 比较当前节点值和前端指针的值 if (currentNode.val ! frontPointer.val) { return false; } // 前端指针向后移动 frontPointer frontPointer.next; } return true; } }复杂度分析时间复杂度O(n)需要递归遍历整个链表空间复杂度O(n)递归调用栈的空间解法四复制到数组 双指针思路将链表值复制到数组中然后使用双指针判断数组是否为回文。代码实现javaclass Solution { public boolean isPalindrome(ListNode head) { // 将链表值复制到数组中 ListInteger values new ArrayList(); ListNode current head; while (current ! null) { values.add(current.val); current current.next; } // 使用双指针判断数组是否为回文 int left 0; int right values.size() - 1; while (left right) { if (!values.get(left).equals(values.get(right))) { return false; } left; right--; } return true; } }复杂度分析时间复杂度O(n)复制到数组O(n)双指针比较O(n/2) ≈ O(n)空间复杂度O(n)需要额外数组存储链表值常见错误与注意事项错误1没有处理奇偶长度差异java// 错误示例没有考虑奇偶长度差异 private ListNode findMiddle(ListNode head) { ListNode slow head; ListNode fast head; while (fast ! null) { // 错误应该检查fast.next slow slow.next; fast fast.next.next; } return slow; }修正javaprivate ListNode findMiddle(ListNode head) { ListNode slow head; ListNode fast head; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; } return slow; }错误2反转链表实现错误修正javaprivate ListNode reverseList(ListNode head) { ListNode pre null; ListNode cur head; while (cur ! null) { ListNode temp cur.next; cur.next pre; pre cur; cur temp; } return pre; }扩展如果要恢复链表怎么办如果需要保持链表原样可以在比较后再次反转恢复javaclass Solution { public boolean isPalindrome(ListNode head) { if (head null || head.next null) return true; // 找到中点 ListNode slow head, fast head; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; } // 反转后半部分 ListNode secondHalf reverseList(slow); // 比较 ListNode p1 head, p2 secondHalf; boolean result true; while (p2 ! null) { if (p1.val ! p2.val) { result false; break; } p1 p1.next; p2 p2.next; } // 恢复链表 reverseList(secondHalf); return result; } private ListNode reverseList(ListNode head) { ListNode prev null, curr head; while (curr ! null) { ListNode nextTemp curr.next; curr.next prev; prev curr; curr nextTemp; } return prev; } }总结方法时间复杂度空间复杂度优点缺点反转后半部分O(n)O(1)空间最优满足进阶要求修改了原链表结构使用栈O(n)O(n)实现简单不修改原链表需要额外空间递归O(n)O(n)代码简洁递归深度可能较大复制到数组O(n)O(n)实现简单需要额外空间推荐使用反转后半部分链表的方法因为空间复杂度为 O(1)满足进阶要求时间复杂度为 O(n)性能良好是面试中最常考的解法相关题目反转链表基础中的基础必须掌握链表的中间结点快慢指针的经典应用回文数字类似的回文判断问题回文字符串字符串版本的回文判断掌握这道题的关键在于理解快慢指针和链表反转这两个核心技巧这两个技巧在链表相关题目中非常常见。