广州艾迪网站建设,项目网格化管理方案,外贸家具网站,必应搜索引擎入口官网这道题一开始想到的方法可能就是patition方法了#xff0c;大概思路我说一下#xff0c;先把这个链表存为数组#xff08;说明其空间复杂度为0#xff08;1#xff09;#xff09;#xff0c;然后在对这个数组进行patition#xff0c;即定义两个指针#xff0c;一个指…这道题一开始想到的方法可能就是patition方法了大概思路我说一下先把这个链表存为数组说明其空间复杂度为01然后在对这个数组进行patition即定义两个指针一个指向数组的-1位置small一个指向数组的arr.length位置big然后来与value比较比较之后有三种情况
1. arr[index] value,这个时候swaparr, index,small主要small要先再交换因为其刚开始是-1
2.arr[index] value,这个时候直接index就行
3. arr[index] value 这个时候swaparrindex--big主要这里的index不用
下面附上源代码public static class Node { private int value; private Node next; public Node(int data) { this.value data; } } public static void printLinkedList(Node node) { System.out.print(LikedList is:); while (node ! null) { System.out.print(node.value ); // 记得是node.value而不是简单的node node node.next; } System.out.println(); } public static Node SmallEqualBig1(Node head, int value) { if (head null) { // 如果为空直接返回head return head; } Node cur head; int i 0; /* 这里是为了求出链表的大小并将其赋值到数组中 */ while (cur ! null) { i; cur cur.next; } Node nodeArr[] new Node[i]; cur head; i 0; while (cur ! null) { nodeArr[i] cur; cur cur.next; i; } /* * patition过程将小于value的值放左边smallindex将大于value的值放右边big--index不变, * 将等于value的值不变index */ arrPatition(nodeArr, value); /* 将patition之后的数组存到链表里面来这个步骤很重要要记住 */ for (i 1; i ! nodeArr.length; i) { nodeArr[i - 1].next nodeArr[i]; } nodeArr[i - 1].next null;// 这个步骤很容易忘记 return nodeArr[0];// 返回头链表 } /* 这个过程非常重要要记住 */ public static void arrPatition(Node nodeArr[], int value) { int small -1; int big nodeArr.length; int index 0; while (index ! big) { if (value nodeArr[index].value) { index; } else if (value nodeArr[index].value) { swap(nodeArr, small, index); } else { swap(nodeArr, --big, index); } } } public static void swap(Node nodeArr[], int i, int j) { Node temp nodeArr[i]; nodeArr[i] nodeArr[j]; nodeArr[j] temp;}进阶题目其实说到底就是增加两个条件
1. 空间复杂度要为01
2. 稳定性要好其实我个人觉得这种方法实现起来更加容易一点不信你们可以看一下源代码/* 这种方法空间复杂度为O1其实这种方法更方便很容易实现并且b格更高因为它的稳定性比上面的方法好 */ public static Node SmallEqualBig2(Node head, int value) { /* * 定义六个指针分别是smallheadsmalltailequalheadequaltailbigheadbigtail还有一个next指针 */ Node sh null; Node st null; Node eh null; Node et null; Node bh null; Node bt null; Node next null; /* 一下是主要实现部分也不难理解 */ while (head ! null) { next head.next;// 将head.next赋值给next下面将head.next指向null head.next null; if (head.value value) { if (sh null) { sh head; st head; } else { st.next head; st head; } } else if (head.value value) { if (eh null) { eh head; et head; } else { et.next head; et head; } } else { if (bh null) { bh head; bt head; } else { bt.next head; bt head; } } head next; // 这一步别忘了将指针往下面移动headnull时停止 } // 连接small部分和equal部分如果shnull就可以连st.next eh if (st ! null) { st.next eh; // 如果中间部分没有与value相等的元素的话就将st赋值给et if (et null) { et st; } } // 连接equal和big部分如果etnull就可以连et.next bh if (et ! null) { et.next bh; } // 返回一个链表的头部,判断small部分null再判断equalnull不然就是bh了 if (sh ! null) { return sh; } else if (eh ! null) { return eh; } else { return bh; } }}
