`
lueye
  • 浏览: 13635 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

面试题:单链表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.linear;
/**
 * 给定头结点和指定结点,删除指定结点在时间复杂度为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)
 * @author xiucai
 */
public class SingleLinkedList_DeleteNode {
	public static<T> void removeNode(Node<T> head,Node<T> node){
		Node<T> p=head;
		if(node.next==null){	//当节点为末尾节点时,遍历。时间复杂度为O(N)
			while(p.next!=node){
				p=p.next;
			}
			p.next=null;
			node=null;
		}else{					//当结点非末尾结点时,复制。时间复杂度为O(1)
			node.data=node.next.data;
			node.next=node.next.next;
		}
	}
	/**
	 * 测试方法
	 * @param args
	 */
	public static void main(String[] args) {
		SingleLinkedList<String> list=new SingleLinkedList<String>();
		for(int i=0;i<10;i++){
			list.append(i+"");
		}
		System.out.println(list);
		Node<String> remove=list.head.next;
		while(remove.next!=null){
			remove=remove.next;
		}
		System.out.println(remove.next);
		removeNode(list.head, remove);
		System.out.println(list);
	}
}

 

0
4
分享到:
评论
5 楼 lueye 2015-01-23  
javalibertine 写道
谢谢!
SingleLinkedList这个类也找不到啊?

SingleLinkedList相当于java中标准的LinkedList类,可以直接使用LinkedList类
4 楼 lueye 2015-01-23  
javalibertine 写道
谢谢!
SingleLinkedList这个类也找不到啊?

这上面的找不到的类是我自己写的,前面练习了一些有关数据结构的线性表和链表的类,这些类在我的博客都可以找到的。
3 楼 javalibertine 2015-01-23  
谢谢!
SingleLinkedList这个类也找不到啊?
2 楼 lueye 2015-01-18  
javalibertine 写道
Node<T>是哪个类???


Node<T> 类 是链表的单个节点类。
代码如下:
package dataStructtion.linear;
/**
* 链表的单个节点
* @author xiucai
* @param <T>
*/
public class Node<T> {
public Object data;//存放数据
public Node<T> next;//后继
//初始化节点
public Node(Object data,Node<T> next){
this.data=data;
this.next=next;
}
public Node(){
this(null,null);
}
//重写toString方法,用于输出
public String toString(){
return this.data.toString();
}
//重写equals方法,用于比较
public boolean equals(Object data){
if (this.data==data)
return true;
if(data instanceof Node){
Node<T> node=(Node<T>)data;
if(this.data==node.data&&this.next==node.next)
return true;
}
return false;
}

}
1 楼 javalibertine 2015-01-18  
Node<T>是哪个类???

相关推荐

    算法分析_有无头结点的单链表的逆序和插入排序问题集源码微软面试题总结

    对于单链表,插入操作的时间复杂度为O(n^2),因为最坏情况下,每个节点都要移动到正确的位置。 在面试中,微软可能会考察你对这两种操作的理解以及如何优化它们。例如,你可以探讨不同的逆序策略(如迭代与递归)的...

    Java常见数据结构面试题(带答案)

    "Java常见数据结构面试题(带答案)" 以下是对Java常见数据结构面试题的知识点总结: 栈和队列 * 栈和队列的共同特点是只允许在端点处插入和删除元素。 * 栈通常采用的两种存储结构是线性存储结构和链表存储结构...

    java数据结构面试题 数据结构试题.pdf

    Java 数据结构面试题涉及到多个核心概念,这些都是编程面试中常见的问题,主要涵盖了时间复杂度、数据结构操作(如链表、栈、排序)以及算法应用(如二分查找、散列表)。下面对这些知识点进行详细解释: 1. 时间...

    很好的数据结构面试题(含答案).docx

    15. 算法的时间复杂度:算法的时间复杂度是指算法执行过程中所需要的基本运算次数。 16. 算法的空间复杂度:算法的空间复杂度是指执行过程中所需要的存储空间。 17. 数据结构的定义:数据结构是一门研究数据的逻辑...

    java数据结构面试题 数据结构试题.docx

    Java 数据结构面试题涵盖了许多核心的...以上是Java数据结构面试题中涉及的主要知识点,包括时间复杂度、链表操作、排序算法、树结构、散列表、图论和队列等。理解和掌握这些内容对于解决实际编程问题和面试至关重要。

    关于链表的一些面试题

    归并排序属于分治算法,其时间复杂度为O(nlogn),空间复杂度为O(1),适用于链表排序,相较于数组排序的归并排序在空间效率上有显著提高。归并排序的主要步骤包括将链表分割成更小的部分进行排序,然后合并这些有序的...

    数据结构面试题 含答案

    ### 数据结构面试题知识点解析 #### 一、数据结构基础概念及特性 1. **栈和队列的特点**: - 栈和队列都属于线性数据结构,它们的共同特点是只允许在端点处进行插入和删除操作。栈遵循后进先出(LIFO)的原则,队列...

    2009计算机考研题:查找链表中倒数第k个结点

    这将使得时间复杂度降低到O(1),但会增加空间复杂度。 总结一下,查找链表中倒数第k个节点的问题主要考察了对链表数据结构的理解和操作,以及双指针算法的应用。`MyLinkList.java`文件中的实现可能包括了链表节点和...

    【数据结构试题】 java数据结构面试题.pdf

    6. 排序算法的时间复杂度:(A)快速排序平均时间复杂度为O(nlogn),(B)堆排序平均时间复杂度也为O(nlogn),(C)归并排序平均时间复杂度同样是O(nlogn),而(D)冒泡排序平均时间复杂度是O(n^2)。 7. 栈的性质:栈是后进...

    数据结构面试题 java面试题

    总的来说,这些面试题覆盖了数据结构的基础知识,包括基本操作、存储结构、遍历方法和算法分析,这些都是理解和设计高效程序的关键。掌握这些概念对于Java开发者来说至关重要,因为它们直接影响到程序的性能和可维护...

    典型数据结构面试题

    ### 数据结构面试题详解 #### 1. 单链表插入操作 在单链表中,在节点`p`前插入节点`s`(值为`e`)的操作涉及到指针的重新指向。正确的步骤是先找到`p`节点的前一个节点`q`,然后更新指针,使得`q-&gt;next`指向`s`,再...

    4399游戏2015校园招聘游戏开发类笔试题.pdf

    8. 单链表的头结点:问题8考查单链表的基本概念和头结点的作用。头结点是一种特殊的结点,它可以简化链表的操作和管理。 9. 时间复杂度的计算:问题9考查时间复杂度的计算。时间复杂度是衡量算法效率的重要指标,它...

    面试题:用 Java 逆序打印链表

    这种方法的时间复杂度为 O(n),其中 n 是链表的长度。下面是实现代码: ```java public class Test05 { public static class Node { int data; Node next; } public static void printLinkReverse(Node head) ...

    LeetCode刷题题解答案(c++).pdf 彻底搞懂了编程算法题,成功拿到了大厂offer!

    - 时间复杂度:O(log(min(m,n))),采用二分查找的方式找到合适的分割点。 - 空间复杂度:O(1),不使用额外空间。 4. **最长连续序列(Longest Consecutive Sequence)** - **问题描述**:给定一个未排序的整数数...

    数据结构面试题

    - **(1)** **算法的时间复杂度**: 衡量算法执行时间的增长率。 - **(2)** **数据的逻辑结构**: 数据元素间的逻辑关系。 - **(3)** **黑盒测试**: 关注程序的输入输出是否符合预期。 - **(4)** **一对多联系**: 一个...

    面试题快慢链表和快慢指针

    腾讯的一道面试题:如何快速找到位置长度单链表的中间节点?普通方法,就是先遍历,在从头找到2/length的中间节点。算法复杂度是:O(3*n/2)。而更快的方法就是利用快慢指针的原理。 快慢链表:利用标尺的思想,设置...

Global site tag (gtag.js) - Google Analytics