面试题：单链表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);
	}
}

 

评论

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>是哪个类？？？