lueye
- 浏览: 13624 次
- 性别:
- 来自: 北京
-
最新评论
-
lueye：
javalibertine 写道谢谢！SingleLinked ...
面试题：单链表O(1)时间复杂度内删除指定结点 -
lueye：
javalibertine 写道谢谢！SingleLinked ...
面试题：单链表O(1)时间复杂度内删除指定结点 -
javalibertine：
谢谢！SingleLinkedList这个类也找不到啊？
面试题：单链表O(1)时间复杂度内删除指定结点 -
cywhoyi：
时间复杂度都是O（N），不管你是O（2N），都是O(N），我的 ...
面试题：找出单链表倒数第N个元素 -
lueye：
javalibertine 写道Node<T>是哪 ...
面试题：单链表O(1)时间复杂度内删除指定结点
文章列表
给定头结点和指定结点，删除指定结点在时间复杂度为O(1)
思路：该节点的前驱无从着手，但后继容易获得。若该节点非末尾结点，则可以把后继结点复制给该节点。代码：node.data=node.next.data;
node.next=node.next.next;
若该节点为末尾结点，即node.next==null时。需从头遍历，此时时间复杂度为O(N)。
综上时间复杂度为：(O(1)*(N-1)+O(N))/N=O(1)。
代码如下：
package dataStructtion.lin ...
第一种方法先求出元素个数，在遍历元素个数-n个，时间复杂度为：O(N+N-n)=O(2N-n)。
第二种设置俩个指针，第一个先走N步，第二个开始走。俩者速度一样，时间复杂度为O(N)。
代码如下：
package dataStructtion.linear;
/**
* 获取单链表倒数第N个元素
* @author xiucai
*/
public class SingleLinkedList_LastN {
/**
* 第一种方法先求出元素个数，在遍历元素个数-n个
* 时间复杂度为：O(N+N-n)=O(2N-n)
* ...
腾讯的面试题：找出未知单链表中点元素？
俩种方法：
第一种：全部遍历算出总长度为length；再遍历length/2个元素。时间复杂度为O(3N/2)
第二种：设置快 ...
算法和数据结构就是编程的一个重要部分，你若失掉了算法和数据结构，你就把一切都失掉了。尤其对于我等应届毕业生来说，能出得了手的也只有这些了。
对于校园招聘来说，互联网公司还是喜欢拿单链表的反转考验我们应届生的。话不多说，代码如下：
package dataStructtion.linear;
/**
* 单链表的反转
* @author xiucai
*
*/
public class SingleLinkedList_Reverse {
public static <T> void reverse(SingleLin ...
数据结构和算法是程序的灵魂，基本的数据结构分为：线性结构、树、图。线性结构又分为顺序实现的线性结构和链式实现的线性结构。链式线性结构是非随机存取结构，其get（）、set（）的时间复杂度是O(N)；若已知要插入或删除的节点位置的话，其insert（）、remove（）的时间复杂度为O(1)。否则需要进行遍历操作，这时insert（）、remove（）的时间复杂度为O(N)。
首次写博客，望各位大牛拍砖来助学习。
以下 是单链表的实现代码：
线性表的抽象数据类型：
package dataStructtion.linear;
/**
...