活跃农民
- 积分
- 740
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2013-5-16
- 最后登录
- 1970-1-1
|
import java.util.Hashtable;
//Implement double LinkedList
class DoubleNode{
DoubleNode next;
DoubleNode previous;
DoubleNode tail;
double data;
DoubleNode(double data){
this.data = data;
next = null;
previous = null;
tail = this;
}
public void addNode(double inputData){
DoubleNode temp = new DoubleNode(inputData);
tail.next = temp;
temp.previous = tail;
tail = tail.next;
}
public String toString(){
StringBuffer toReturn = new StringBuffer();
//pointer
DoubleNode current = this;
while(current != null){
//if it is the end node, append "data" to the buffer
if(current.next == null){
toReturn.append(current.data);
}
//if it is not the end, append "data - " to the buffer
else{
toReturn.append(current.data + " <-> ");
}
current = current.next;
}
return toReturn.toString();
}
}
/**
* Given a double LinkedList, you return the head of a new double
* LinkedList where all the node that is not repeated is deleted
*
* Sample input:
* 1.1<->2.5<->1.1<->3.1<->4.10<->2.50
*
* Sample output:
* 1.1<->2.5<->1.1<->2.50
*
* @author Ziliang Zhu
*
*/
public class DoubleLinkedlistRepetitionSift {
Hashtable<Double, Boolean> myHash;
public DoubleLinkedlistRepetitionSift(){
myHash = new Hashtable<Double, Boolean>();
}
public DoubleNode onlyKeepRepeated(DoubleNode myHead){
DoubleNode current = myHead;
DoubleNode toReturn = null;
//Read through the list the first time
while(current != null){
//There is no such node, put it in, set false
if(myHash.get(current.data) == null){
myHash.put(current.data, false);
}
//There is already such a node, remove it, put it in, set true
else if(myHash.get(current.data) == false){
myHash.remove(current.data);
myHash.put(current.data, true);
}
//update current
current = current.next;
}
//Reset current
current = myHead;
//Read through the list the second time
while(current != null){
//When the node is repeated, add it to the double LinkedList
//Use hashtable to determine is the node is needed
if(myHash.get(current.data) == true){
//copy and paste nodes
if(toReturn != null){
toReturn.addNode(current.data);
}
else{
toReturn = new DoubleNode(current.data);
}
}
//update current
current = current.next;
}
return toReturn;
}
}
补充内容 (2013-10-19 14:03):
我把地下室楼层的想法试着用java写了一下,主要是想请哪位有耐心读的提出些建议,各位见笑 |
|