怎么制作网站?,新蔡县城乡建设局网站,茂名小学网站建设,WordPress小程序二次开发一、查找单链表中间结点
1、简单查找 先遍历获取单链表单长度n#xff0c;然后通过计算得到中间结点为n/2#xff0c;然后查找下标为n/2的元素。
2、优化查找 先设置记录点fast、slow#xff0c;下标均从0开始#xff0c;fast走两步#xff0c;slow走一步#xff0c;同…一、查找单链表中间结点
1、简单查找 先遍历获取单链表单长度n然后通过计算得到中间结点为n/2然后查找下标为n/2的元素。
2、优化查找 先设置记录点fast、slow下标均从0开始fast走两步slow走一步同时遍历两个记录点直到fast的值为nullslow是中间结点。
单链表结点 package cn.edu.scau.mk;/**** author MK* param T*/
public class NodeT {private T data;private NodeT next null;public Node(T data) {this.data data;}public T getData() {return data;}public void setData(T data) {this.data data;}public NodeT getNext() {return next;}public void setNext(NodeT next) {this.next next;}} View Code链表 package cn.edu.scau.mk;import java.util.Comparator;/**** author MK* param T*/
public class LinkedListT {protected NodeT head null;/*** 添加** param data*/public void add(T data) {//头结点为nullif (head null) {head new Node(data);return;}//寻找末结点NodeT curNode head;while (curNode.getNext() ! null) {curNode curNode.getNext();}curNode.setNext(new Node(data));//添加结点}/*** 删除** param index 下标,从0开始* return*/public boolean delete(int index) {//没有数据if (head null) {return false;}//删除头结点if (index 0) {head head.getNext();}NodeT curNode head;int i 1;while (curNode.getNext() ! null) {if (i index) {curNode.setNext(curNode.getNext().getNext());return true;}i;curNode curNode.getNext();}throw new IndexOutOfBoundsException(Index: index, Size: i);}/*** 长度** return*/public int length() {int len 0;NodeT curNode head;while (curNode ! null) {len;curNode curNode.getNext();}return len;}/*** 查找* param index 位置* return */public T get(int index) {NodeT curNode head;int i 0;while (curNode ! null) {if (i index) {return curNode.getData();}i;curNode curNode.getNext();}throw new IndexOutOfBoundsException(Index: index, Size: i);}/*** 排序* param comparator 比较器*/public void sort(ComparatorT comparator) {//没有数据if (head null) {return;}NodeT curNode head;NodeT nextNode;NodeT minNode;while (curNode.getNext() ! null) {minNode curNode; //默认最小结点为当前结点nextNode curNode.getNext(); //下一个结点while (nextNode ! null) {//比当前结点小记录最小结点if(comparator.compare(curNode.getData(), nextNode.getData())0){minNodenextNode;}nextNodenextNode.getNext(); //继续与下一个结点比较}//最小结点不是当前结点交换数据if(minNode!curNode){T datacurNode.getData();curNode.setData(minNode.getData());minNode.setData(data);}curNodecurNode.getNext(); //移至下一个结点}}/*** 打印输出*/public void print() {NodeT curNode head;while (curNode!null) { System.out.print(curNode.getData() );curNodecurNode.getNext();}System.out.println();}
} View Code二、简单查找 package cn.edu.scau.mk;/**** author MK* param T*/
public class MidLinkedListT extends LinkedListT {/*** 获取中间结点** return*/public T getMid() {if (head null) {throw new NullPointerException(no middle element);}NodeT curNode head;int lenlength()/2;for (int i 0; i len ; i) {curNodecurNode.getNext();}return curNode.getData();}
} 三、优化查找 package cn.edu.scau.mk;/**** author MK* param T*/
public class MidLinkedListT extends LinkedListT {/*** 获取中间结点** return*/public T getMid() {//没有数据if (head null) {throw new NullPointerException(no middle element);}NodeT fast head;NodeT slow head;while (fast ! null fast.getNext() ! null) {fast fast.getNext().getNext();//快记录点走两步slow slow.getNext(); //慢记录点走一步}return slow.getData();}
}
