嘉兴网站建设方案微信朋友圈广告怎么推广

嘉兴网站建设方案,微信朋友圈广告怎么推广,wordpress页面参数,上海知名建站公司给一个链表#xff0c;判断这个链表是否为回文链表。能否使用O(1)的空间复杂度解决问题#xff1f;思路1#xff1a;使用辅助空间#xff0c;我们这里给出了使用动态数组作为检查表#xff0c;给出了两种实现方式#xff0c;但是这种实现方式效率不高。​ public class L…给一个链表判断这个链表是否为回文链表。能否使用O(1)的空间复杂度解决问题思路1使用辅助空间我们这里给出了使用动态数组作为检查表给出了两种实现方式但是这种实现方式效率不高。​ public class ListNode { public int val; public ListNode next; public ListNode(int x) { this.val x; this.next null; } public static ListNode createList(int[] nums) { if(null nums || 0 nums.length) return null; ListNode head new ListNode(nums[0]); ListNode needle head; for(int i 1; i nums.length;i) { ListNode node new ListNode(nums[i]); needle.next node; needle needle.next; needle.next null; } return head; } }import java.util.ArrayList; import java.util.List; class Solution { public boolean isPalindrome(ListNode head) { if (null head || null head.next) return true; ListInteger all new ArrayListInteger(); while (head ! null) { all.add(head.val); head head.next; } for (int i 0; i all.size() / 2; i) { if ((int) all.get(i) ! (int) all.get(all.size() - 1 - i)) return false; } return true; } public static void main(String[] args) { int[] nums1 { 1, 2, 4, 2, 1 }; ListNode l1 ListNode.createList(nums1); boolean result new Solution().isPalindrome(l1); System.out.print(result); } }思路2使用O(1)空间复杂度即需要的临时空间较少且跟链表长度没有关系我们这里给出了两种实现方式实现思路相同。使用快慢指针找到中间结点位置一种是反转链表的前半部分一种是反转链表的后半部分反转后半部分更容易实现效率也要高。class Solution { public boolean isPalindrome(ListNode head) { if (null head || null head.next) return true; // 找中间位置开始 ListNode fast head; ListNode faster head; while (faster ! null faster.next ! null) { fast fast.next; faster faster.next.next; } // 找中间位置结束 // 反转fast之前的所有元素 // pre指向当前结点的前驱反转后第一个结点的后继 ListNode pre null; // 指向当前遍历的结点 ListNode cur head; while (cur ! fast) { // 记录当前结点的下一个结点否则执行下一条一句就丢了后面没有反转的剩余结点 ListNode next cur.next; // 真正的反转指针变化方向因为链表最后一个结点的next为空这也是为什么pre的初始值为null cur.next pre; // 向后继续遍历剩余未反转的结点pre和cur均要向后移动一位 pre cur; cur next; } // 到此cur指向fast而pre指向了最后一个被反转的结点也就是新链表的头 // 比较元素值是否相同开始 // 链表元素个数为奇数个的情况 if (null ! faster null faster.next)// odd fast fast.next; // 比较反转后的[pre,fast)与[fast,tail]到链表尾部 while (pre ! null fast ! null) { if (pre.val ! fast.val) return false; pre pre.next; fast fast.next; } // 比较元素值是否相同结束 return true; } public static void main(String[] args) { int[] nums1 { 1, 2, 4, 2, 1 }; ListNode l1 ListNode.createList(nums1); boolean result new Solution().isPalindrome(l1); System.out.print(result); } }