企业官网建设流程全解析

无锡企业建站程序,360建筑网撤销自己的简历怎么撤销,西安建网站网站推广,计算机外包公司链表的中间结点 问题描述 给定一个非空单链表的头结点 head#xff0c;返回链表的中间结点。 如果有两个中间结点#xff0c;则返回第二个中间结点。 链表节点定义#xff1a; class ListNode {int val;ListNode next;ListNode() {}ListNode(int val) { this.val val; }Lis…链表的中间结点问题描述给定一个非空单链表的头结点head返回链表的中间结点。如果有两个中间结点则返回第二个中间结点。链表节点定义classListNode{intval;ListNodenext;ListNode(){}ListNode(intval){this.valval;}ListNode(intval,ListNodenext){this.valval;this.nextnext;}}示例输入:[1,2,3,4,5]输出:[3,4,5]解释:中间结点是值为3的结点 输入:[1,2,3,4,5,6]输出:[4,5,6]解释:有两个中间结点值分别为3和4返回第二个值为4的结点算法思路快慢指针核心思想使用两个指针slow慢指针和fast快指针slow每次移动 1 步fast每次移动 2 步当fast到达链表末尾时slow正好在中间位置关键对于奇数长度slow在第 (n1)/2 个位置真正的中间对于偶数长度slow在第 n/2 1 个位置第二个中间结点终止条件fast null链表长度为偶数fast.next null链表长度为奇数循环条件fast ! null fast.next ! null代码实现方法一快慢指针/** * Definition for singly-linked list. */classListNode{intval;ListNodenext;ListNode(){}ListNode(intval){this.valval;}ListNode(intval,ListNodenext){this.valval;this.nextnext;}}classSolution{/** * 找到链表的中间结点如果有两个中间结点返回第二个 * * param head 链表头结点 * return 中间结点 * * 算法思路快慢指针 * 1. slow每次移动1步fast每次移动2步 * 2. 当fast到达末尾时slow正好在中间 * 3. 处理奇偶长度的统一逻辑 */publicListNodemiddleNode(ListNodehead){// 初始化快慢指针ListNodeslowhead;ListNodefasthead;// 快指针每次走2步慢指针每次走1步// 当快指针到达末尾时慢指针就在中间while(fast!nullfast.next!null){slowslow.next;// 慢指针走1步fastfast.next.next;// 快指针走2步}returnslow;}}方法二两次遍历classSolution{/** * 两次遍历 * 1. 第一次遍历计算链表长度 * 2. 第二次遍历找到中间位置 */publicListNodemiddleNode(ListNodehead){// 第一次遍历计算链表长度intlength0;ListNodecurrenthead;while(current!null){length;currentcurrent.next;}// 计算中间位置第二个中间结点intmiddlelength/2;// 第二次遍历找到中间结点currenthead;for(inti0;imiddle;i){currentcurrent.next;}returncurrent;}}方法三数组存储classSolution{/** * 使用数组存储所有结点然后直接返回中间位置的结点 */publicListNodemiddleNode(ListNodehead){ListListNodenodesnewArrayList();ListNodecurrenthead;// 将所有结点存储到数组中while(current!null){nodes.add(current);currentcurrent.next;}// 返回中间结点returnnodes.get(nodes.size()/2);}}算法分析时间复杂度快慢指针O(n)只需要一次遍历快指针走 n 步慢指针走 n/2 步两次遍历O(n)第一次遍历 n 步第二次遍历 n/2 步总计 1.5n 步数组存储O(n)一次遍历存储然后 O(1) 访问空间复杂度快慢指针O(1)只使用两个指针变量两次遍历O(1)只使用常数额外空间数组存储O(n)需要存储所有结点的引用算法过程1奇数长度链表 [1,2,3,4,5]快慢指针初始: slow1, fast1 第1次循环: - slow slow.next 2 - fast fast.next.next 3 - 状态: slow2, fast3 第2次循环: - slow slow.next 3 - fast fast.next.next 5 - 状态: slow3, fast5 第3次循环检查: - fast.next null循环终止 返回 slow 32偶数长度链表 [1,2,3,4,5,6]快慢指针初始: slow1, fast1 第1次循环: - slow 2, fast 3 第2次循环: - slow 3, fast 5 第3次循环: - slow 4, fast null (5.next.next null) 循环终止条件: fast null 返回 slow 4测试用例importjava.util.*;publicclassTest{// 创建链表publicstaticListNodecreateList(int[]values){if(values.length0)returnnull;ListNodeheadnewListNode(values[0]);ListNodecurrenthead;for(inti1;ivalues.length;i){current.nextnewListNode(values[i]);currentcurrent.next;}returnhead;}// 将链表转换为数组用于输出publicstaticint[]listToArray(ListNodehead){ListIntegervaluesnewArrayList();ListNodecurrenthead;while(current!null){values.add(current.val);currentcurrent.next;}returnvalues.stream().mapToInt(i-i).toArray();}publicstaticvoidmain(String[]args){SolutionsolutionnewSolution();// 测试用例1奇数长度ListNodehead1createList(newint[]{1,2,3,4,5});ListNoderesult1solution.middleNode(head1);System.out.println(Test 1: Arrays.toString(listToArray(result1)));// [3,4,5]// 测试用例2偶数长度ListNodehead2createList(newint[]{1,2,3,4,5,6});ListNoderesult2solution.middleNode(head2);System.out.println(Test 2: Arrays.toString(listToArray(result2)));// [4,5,6]// 测试用例3单个结点ListNodehead3createList(newint[]{1});ListNoderesult3solution.middleNode(head3);System.out.println(Test 3: Arrays.toString(listToArray(result3)));// [1]// 测试用例4两个结点ListNodehead4createList(newint[]{1,2});ListNoderesult4solution.middleNode(head4);System.out.println(Test 4: Arrays.toString(listToArray(result4)));// [2]// 测试用例5三个结点ListNodehead5createList(newint[]{1,2,3});ListNoderesult5solution.middleNode(head5);System.out.println(Test 5: Arrays.toString(listToArray(result5)));// [2,3]// 测试用例6四个结点ListNodehead6createList(newint[]{1,2,3,4});ListNoderesult6solution.middleNode(head6);System.out.println(Test 6: Arrays.toString(listToArray(result6)));// [3,4]// 测试用例7大链表int[]largeArraynewint[1000];for(inti0;i1000;i){largeArray[i]i1;}ListNodehead7createList(largeArray);ListNoderesult7solution.middleNode(head7);System.out.println(Test 7: result7.val);// 501 (1000/2 1 501)// 测试用例8边界值ListNodehead8createList(newint[]{100000});ListNoderesult8solution.middleNode(head8);System.out.println(Test 8: Arrays.toString(listToArray(result8)));// [100000]}}关键点快慢指针慢指针每次1步快指针每次2步循环终止条件fast ! null fast.next ! null确保快指针可以安全地移动2步奇偶长度统一处理偶数长度时返回第二个中间结点常见问题为什么快指针要检查 fast.next ! null快指针每次要移动2步fast.next.next如果fast.next null那么fast.next.next会抛出 NullPointerException快慢指针的其他应用检测链表是否有环Floyd判圈算法找到链表的倒数第k个结点分割链表为两半