双向链接列表
我创建了双向圆形链接列表。双向链接列表
我需要知道每个节点到头部的距离。
因为当我必须删除或获取一个节点与特定键,如果2个节点具有相同的密钥和相同的距离,两者都必须被删除或获得,否则必须删除最接近头节点。
我不知道如何计算距离,因为是圆形的......
这样这个链表工作的插入。
所有节点后头部去。
实施例:
1)头部
2)头 - A(插入的)
3)机头-BA(插入的B)
4)头-CBA(插入的C)
现在,我只做一个正常的取消没有距离。 这是我的代码。
/* Function to delete node with the key */
public void deleteWithKey(int key) {
if (key == head.getData()) {
if (size == 1) {
head = null;
end = null;
size = 0;
return;
}
head = head.getLinkNext();
head.setLinkPrev(end);
end.setLinkNext(head);
size--;
return;
}
if (key == end.getData()) {
end = end.getLinkPrev();
end.setLinkNext(head);
head.setLinkPrev(end);
size--;
}
Node current = head.getLinkNext();
for (int i = 2; i < size; i++) {
if (key == current.getData()) {
Node p = current.getLinkPrev();
Node n = current.getLinkNext();
p.setLinkNext(n);
n.setLinkPrev(p);
size--;
return;
}
current = current.getLinkNext();
}
System.out.println("Don't exist a node with this key");
}
感谢所有。
这是我所做的最终工作代码。
你有没有改进?
感谢所有的帮助。
复杂= O(n)的
/* Function to delete node with the key */
public void deleteWithKey(int key) {
if (key == head.getData()) {
if (size == 1) {
head = null;
end = null;
size = 0;
return;
}
head = head.getLinkNext();
head.setLinkPrev(end);
end.setLinkNext(head);
size--;
return;
}
if (key == end.getData()) {
end = end.getLinkPrev();
end.setLinkNext(head);
head.setLinkPrev(end);
size--;
}
Node next = head;
Node back = head;
while (next != end) {
next = next.getLinkNext();
back = back.getLinkPrev();
if ((key == next.getData()) && (key == back.getData()) && (next != back)) {
Node p = next.getLinkPrev();
Node n = next.getLinkNext();
Node p1 = back.getLinkPrev();
Node n1 = next.getLinkNext();
p.setLinkNext(n);
n.setLinkPrev(p);
p1.setLinkPrev(n1);
n1.setLinkPrev(p1);
size -= 2;
return;
}
if ((key == next.getData()) && (next != back)) {
Node p = next.getLinkPrev();
Node n = next.getLinkNext();
p.setLinkNext(n);
n.setLinkPrev(p);
size--;
return;
}
if ((key == next.getData()) && (next == back)) {
Node p = next.getLinkPrev();
Node n = next.getLinkNext();
p.setLinkNext(n);
n.setLinkPrev(p);
size--;
return;
}
}
System.out.println("Don't exist a node with this key");
}
这是我能想到的解决问题的伪代码。
鉴于head
,
// no data
if(head==null) return;
// next and prev are always at same distance
next = head;
prev = head.prev;
// ensure nodes are not same or crossed half way through the list
while (next == prev || next.prev == prev){
// delete nodes if values are same
if (next.val == prev.val){
if(next!=head) {
next.prev.next = next.next;
next.next.prev = next.prev;
prev.prev.next = prev.next;
prev.next.prev = prev.prev;
}
// list has only two nodes
else if(head.next==prev){
head = null;
return;
// remove head and its prev node
else{
head = head.next;
head.prev = prev.next;
head.prev.next = head
}
}
// traverse through the list
next = next.next
prev = prev.prev
}
该类的next和prev参数节点可帮助我们滚动节点 –
(项目文本)说,头是插入的第一个节点,并且末尾将始终是为插入模式插入的第二个节点。 –
他们是数据节点。你应该保留两个空指针,这些数据节点只是你的impl代码 –
你其实并不需要知道的距离。相反,你需要找到最接近头的。
因为它是一个循环双向链表,这个任务很简单:
- 定义两个变量
a
和b
,初始化两个头 - 如果其中任何一个目标,删除匹配的节点和出口
- 分配
a = a.next
和b = b.previous
- 转到2
没错。我没有想过。我喜欢这个解决方案。我测试得很快。 –
为什么它来计算的距离的问题? –
因为是循环的。每个节点都链接到左侧和右侧。我需要知道从头到每个节点的距离。 –
示例:我有一个列表Head-B-A,B和A的距离相同。因为A与Head关联。将是A 头 B A –