双向循环链表
Doubly Circular Linked List
我创建了一个双向循环链表。
我需要知道每个节点到头部的距离。
因为当我必须删除或获取具有特定键的节点时,如果2个节点具有相同的键和相同的距离,则都必须删除或获取,否则必须删除最接近头部的节点。
我不知道如何计算距离,因为是圆形的...
这个Linked List的插入是这样的。
所有节点都在 Head 之后。
示例:
1) 头
2) Head-A (插入A)
3) Head-B-A (插入B)
4) Head-C-B-A (插入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");
}
感谢大家。
这是我能想到的解决问题的伪代码。
给定 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
}
其实你不需要知道距离。相反,您需要找到最接近头部的。
因为它是一个循环双向链表,这个任务很简单:
- 定义两个变量
a
和b
,将两者初始化为head
- 如果其中一个是目标,删除匹配的节点并退出
- 分配
a = a.next
和 b = b.previous
- 转到 2
这是我完成的最终工作代码。
你有进步吗?
感谢大家的帮助。
复杂度 = 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");
}
我创建了一个双向循环链表。
我需要知道每个节点到头部的距离。
因为当我必须删除或获取具有特定键的节点时,如果2个节点具有相同的键和相同的距离,则都必须删除或获取,否则必须删除最接近头部的节点。
我不知道如何计算距离,因为是圆形的...
这个Linked List的插入是这样的。
所有节点都在 Head 之后。
示例:
1) 头
2) Head-A (插入A)
3) Head-B-A (插入B)
4) Head-C-B-A (插入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");
}
感谢大家。
这是我能想到的解决问题的伪代码。
给定 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
}
其实你不需要知道距离。相反,您需要找到最接近头部的。
因为它是一个循环双向链表,这个任务很简单:
- 定义两个变量
a
和b
,将两者初始化为head - 如果其中一个是目标,删除匹配的节点并退出
- 分配
a = a.next
和b = b.previous
- 转到 2
这是我完成的最终工作代码。
你有进步吗?
感谢大家的帮助。
复杂度 = 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");
}