删除循环链表的尾部元素
Deleting the rear element of a circular linked list
我正在 java 中的循环 linked 列表中尝试各种方法,其中之一是删除后面的元素。我很确定我的逻辑是正确的,但我认为我的代码有问题。
逻辑是浏览列表直到cur.next
在后面的元素之前,然后删除它。然后我应该 link 将新的后部元素放到头部并初始化新的后部。
我没有收到错误,只是删除了错误的元素。
这就是我得到的:
输入:8 | 4 | -8 | 5 | 10 | 3 | 4 | 8 |
输出:8 | 4 | 5 | 10 | 3 | 4 | 8 |
这是方法:
public void deleteAtRear() {
if(this.head == null)
return;
Element cur = this.head;
while(cur.next != this.rear) {
cur = cur.next;
}
cur.next = cur.next.next;
this.rear = cur;
}
这是全部class:
public class CircularLinkedList {
class Element{
int data; // int type used as example
Element next; // reference of the successor
Element(int value) {
this.data = value;
this.next = this;
}
}
private Element head = null;
private Element rear = null;
public CircularLinkedList() {
this.head = this.rear = null;
}
public boolean isEmpty() {
return head == null;
}
public boolean findValue(int value) {
Element cur = this.head;
while(cur != null) {
if (cur.data == value)
return true;
cur = cur.next;
}
return false;
}
public int countValue(int value) {
int c = 0; // counter
Element cur = this.head;
if(cur == null)
return 0;
do {
if(cur.data == value)
c++;
cur = cur.next;
}while (cur != this.head);
return c;
}
@Override
public String toString() {
String str = "";
Element cur = this.head;
if(cur == null)
return "The list is empty";
do {
str += cur.data + " | ";
cur = cur.next;
}while (cur != this.head);
return str;
}
public void insert(int value) {
Element tmp = new Element (value);
//special case: empty list
if(this.head == null) {
this.head = tmp;
this.rear = tmp;
}else { // general case
tmp.next = this.head.next;
this.head.next = tmp;
this.rear = tmp.next;
}
}
public void deleteAtHead() {
if(this.head == null)
return;
Element cur = this.head;
while(cur.next != this.head) {
cur = cur.next;
}
cur.next = cur.next.next;
this.head = this.head.next;
return ;
}
public void deleteAtRear() {
if(this.head == null)
return;
Element cur = this.head;
// Element prev = null;
while(cur.next != this.rear) {
// prev = cur;
cur = cur.next;
}
cur.next = cur.next.next;
this.rear = cur;
}
public boolean delete(int value) {
Element cur = this.head;
if(this.head.data == value) { //if the node to be deleted is head node
while(cur.next != this.head) { //iterate till the last node i.e. the node which is pointing to head
cur = cur.next;
}
cur.next = cur.next.next; // update current node pointer to next node of head
this.head = this.head.next; //update head node
return true;
}
else { // if node to be deleted is other than head node
Element prev = cur; // track previous node from current (node)
while(cur.data != value) { // find the node
prev = cur;
cur = cur.next;
}
prev.next = cur.next; //updating next field of previous node to next of current node.current node deleted
return true;
}
}
public void deleteEven() {
// if(this.head == null)
// return;
//
// //case of deleting the head
// if(this.head.data % 2 == 0) {
// this.head.next = this.head;
// this.rear.next = this.head;
// if(this.head == null)
// this.rear = null;
// }
//
// Element cur = this.head;
// Element prev = cur;
// while(cur != this.head) {
// prev = cur;
// cur = cur.next;
// }
// prev.next = cur.next;
if(this.head == null)
return;
Element cur = this.head;
while(cur.next != this.head) {
if(cur.data % 2 == 0)
this.delete(cur.data);
cur = cur.next;
}
}
public void deleteLastOccurence(int value) {
Element cur = this.head;
Element prev = null;
Element tmp = null;
if(this.head == null)
return;
// if(this.head.data == value) {
// this.head = null;
// return;
// }
while(cur != this.rear) {
while(cur.next != this.head && cur.next.data == value) {
prev = cur;
tmp = cur.next;
}
cur = cur.next;
}
prev.next = tmp.next;
}
public void deleteAllOccurrences(int value) {
Element cur = this.head;
Element next = null;
if (cur.data == value) {
cur = cur.next;
this.head = cur;
}
do {
next = cur.next;
if (next.data == value) {
cur.next = next.next;
}
cur = next;
} while (cur != this.head);
}
public CircularLinkedList union(CircularLinkedList a, CircularLinkedList b) {
Element curA = a.head;
Element curB = b.head;
CircularLinkedList c = new CircularLinkedList();
// do {
// if(curA.data < curB.data) {
// c.insert(curA.data);
// curA = curA.next;
// }else {
// c.insert(curB.data);
// curB = curB.next;
// }
// }while(curA != a.rear && curB != b.rear);
do {
c.insert(curA.data);
curA = curA.next;
}while(curA != a.rear);
do {
c.insert(curB.data);
curB = curB.next;
}while(curB != b.rear);
return c;
}
//
//
// public CircularLinkedList inter(CircularLinkedList a, CircularLinkedList b) {
//
// }
// public boolean isEqualTo(CircularLinkedList a) {
//
// }
public int countOddNbrs() {
if(this.head == null)
return 0;
int c = 0;
Element cur = this.head;
do {
if(cur.data % 2 != 0)
c++;
cur = cur.next;
}while(cur != this.head);
return c;
}
// public int findLastOccurence(int value) {
//
// }
public static void main(String[] args) {
CircularLinkedList list = new CircularLinkedList();
CircularLinkedList list1 = new CircularLinkedList();
CircularLinkedList list2 = new CircularLinkedList();
list.insert(8);
list.insert(8);
list.insert(4);
list.insert(3);
list.insert(10);
list.insert(5);
list.insert(-8);
list.insert(4);
System.out.println(list);
list1.insert(5);
list1.insert(1);
list1.insert(3);
list1.insert(7);
list1.insert(0);
list1.insert(6);
list1.insert(-4);
list1.insert(1);
// System.out.println(list1);
// System.out.println(list.findValue(2)); // working
// list.delete(8); // working
// System.out.println(list);
// System.out.println(list.countOddNbrs()); //working
// list.deleteEven(); // working
// System.out.println(list);
// list.deleteAtHead(); // working
// System.out.println(list);
list.deleteAtRear(); // working
System.out.println(list);
// list.deleteLastOccurence(4); //not working
// System.out.println(list);
// list.deleteAllOccurrences(8); // working
// System.out.println(list);
// list2.union(list, list1); //not working
// System.out.println(list2);
}
}
问题出在 insert
方法中,在一般情况下您没有正确分配引用(假设在列表末尾插入 tmp
):
tmp.next
应指向第一个元素 (this.head
) 以具有适当的循环 [A]
this.rear.next
(不是this.head.next
)应该指向新元素[B]
this.rear
应该指向被插入的元素,因为它现在是列表的新的最后一个元素 [C]
此外,在特殊情况 [D].[=19= 中插入空列表时,您不会将自引用分配给列表的单个元素]
这是 insert
方法的一个工作示例:
public void insert(int value) {
final Element tmp = new Element(value);
if (this.head == null) { // special case: empty list
tmp.next = tmp; // <-- [D]
this.head = tmp;
this.rear = tmp;
} else { // general case
tmp.next = this.head; // <-- [A]
this.rear.next = tmp; // <-- [B]
this.rear = tmp; // <-- [C]
}
}
我正在 java 中的循环 linked 列表中尝试各种方法,其中之一是删除后面的元素。我很确定我的逻辑是正确的,但我认为我的代码有问题。
逻辑是浏览列表直到cur.next
在后面的元素之前,然后删除它。然后我应该 link 将新的后部元素放到头部并初始化新的后部。
我没有收到错误,只是删除了错误的元素。
这就是我得到的:
输入:8 | 4 | -8 | 5 | 10 | 3 | 4 | 8 |
输出:8 | 4 | 5 | 10 | 3 | 4 | 8 |
这是方法:
public void deleteAtRear() {
if(this.head == null)
return;
Element cur = this.head;
while(cur.next != this.rear) {
cur = cur.next;
}
cur.next = cur.next.next;
this.rear = cur;
}
这是全部class:
public class CircularLinkedList {
class Element{
int data; // int type used as example
Element next; // reference of the successor
Element(int value) {
this.data = value;
this.next = this;
}
}
private Element head = null;
private Element rear = null;
public CircularLinkedList() {
this.head = this.rear = null;
}
public boolean isEmpty() {
return head == null;
}
public boolean findValue(int value) {
Element cur = this.head;
while(cur != null) {
if (cur.data == value)
return true;
cur = cur.next;
}
return false;
}
public int countValue(int value) {
int c = 0; // counter
Element cur = this.head;
if(cur == null)
return 0;
do {
if(cur.data == value)
c++;
cur = cur.next;
}while (cur != this.head);
return c;
}
@Override
public String toString() {
String str = "";
Element cur = this.head;
if(cur == null)
return "The list is empty";
do {
str += cur.data + " | ";
cur = cur.next;
}while (cur != this.head);
return str;
}
public void insert(int value) {
Element tmp = new Element (value);
//special case: empty list
if(this.head == null) {
this.head = tmp;
this.rear = tmp;
}else { // general case
tmp.next = this.head.next;
this.head.next = tmp;
this.rear = tmp.next;
}
}
public void deleteAtHead() {
if(this.head == null)
return;
Element cur = this.head;
while(cur.next != this.head) {
cur = cur.next;
}
cur.next = cur.next.next;
this.head = this.head.next;
return ;
}
public void deleteAtRear() {
if(this.head == null)
return;
Element cur = this.head;
// Element prev = null;
while(cur.next != this.rear) {
// prev = cur;
cur = cur.next;
}
cur.next = cur.next.next;
this.rear = cur;
}
public boolean delete(int value) {
Element cur = this.head;
if(this.head.data == value) { //if the node to be deleted is head node
while(cur.next != this.head) { //iterate till the last node i.e. the node which is pointing to head
cur = cur.next;
}
cur.next = cur.next.next; // update current node pointer to next node of head
this.head = this.head.next; //update head node
return true;
}
else { // if node to be deleted is other than head node
Element prev = cur; // track previous node from current (node)
while(cur.data != value) { // find the node
prev = cur;
cur = cur.next;
}
prev.next = cur.next; //updating next field of previous node to next of current node.current node deleted
return true;
}
}
public void deleteEven() {
// if(this.head == null)
// return;
//
// //case of deleting the head
// if(this.head.data % 2 == 0) {
// this.head.next = this.head;
// this.rear.next = this.head;
// if(this.head == null)
// this.rear = null;
// }
//
// Element cur = this.head;
// Element prev = cur;
// while(cur != this.head) {
// prev = cur;
// cur = cur.next;
// }
// prev.next = cur.next;
if(this.head == null)
return;
Element cur = this.head;
while(cur.next != this.head) {
if(cur.data % 2 == 0)
this.delete(cur.data);
cur = cur.next;
}
}
public void deleteLastOccurence(int value) {
Element cur = this.head;
Element prev = null;
Element tmp = null;
if(this.head == null)
return;
// if(this.head.data == value) {
// this.head = null;
// return;
// }
while(cur != this.rear) {
while(cur.next != this.head && cur.next.data == value) {
prev = cur;
tmp = cur.next;
}
cur = cur.next;
}
prev.next = tmp.next;
}
public void deleteAllOccurrences(int value) {
Element cur = this.head;
Element next = null;
if (cur.data == value) {
cur = cur.next;
this.head = cur;
}
do {
next = cur.next;
if (next.data == value) {
cur.next = next.next;
}
cur = next;
} while (cur != this.head);
}
public CircularLinkedList union(CircularLinkedList a, CircularLinkedList b) {
Element curA = a.head;
Element curB = b.head;
CircularLinkedList c = new CircularLinkedList();
// do {
// if(curA.data < curB.data) {
// c.insert(curA.data);
// curA = curA.next;
// }else {
// c.insert(curB.data);
// curB = curB.next;
// }
// }while(curA != a.rear && curB != b.rear);
do {
c.insert(curA.data);
curA = curA.next;
}while(curA != a.rear);
do {
c.insert(curB.data);
curB = curB.next;
}while(curB != b.rear);
return c;
}
//
//
// public CircularLinkedList inter(CircularLinkedList a, CircularLinkedList b) {
//
// }
// public boolean isEqualTo(CircularLinkedList a) {
//
// }
public int countOddNbrs() {
if(this.head == null)
return 0;
int c = 0;
Element cur = this.head;
do {
if(cur.data % 2 != 0)
c++;
cur = cur.next;
}while(cur != this.head);
return c;
}
// public int findLastOccurence(int value) {
//
// }
public static void main(String[] args) {
CircularLinkedList list = new CircularLinkedList();
CircularLinkedList list1 = new CircularLinkedList();
CircularLinkedList list2 = new CircularLinkedList();
list.insert(8);
list.insert(8);
list.insert(4);
list.insert(3);
list.insert(10);
list.insert(5);
list.insert(-8);
list.insert(4);
System.out.println(list);
list1.insert(5);
list1.insert(1);
list1.insert(3);
list1.insert(7);
list1.insert(0);
list1.insert(6);
list1.insert(-4);
list1.insert(1);
// System.out.println(list1);
// System.out.println(list.findValue(2)); // working
// list.delete(8); // working
// System.out.println(list);
// System.out.println(list.countOddNbrs()); //working
// list.deleteEven(); // working
// System.out.println(list);
// list.deleteAtHead(); // working
// System.out.println(list);
list.deleteAtRear(); // working
System.out.println(list);
// list.deleteLastOccurence(4); //not working
// System.out.println(list);
// list.deleteAllOccurrences(8); // working
// System.out.println(list);
// list2.union(list, list1); //not working
// System.out.println(list2);
}
}
问题出在 insert
方法中,在一般情况下您没有正确分配引用(假设在列表末尾插入 tmp
):
tmp.next
应指向第一个元素 (this.head
) 以具有适当的循环 [A]this.rear.next
(不是this.head.next
)应该指向新元素[B]this.rear
应该指向被插入的元素,因为它现在是列表的新的最后一个元素 [C]
此外,在特殊情况 [D].[=19= 中插入空列表时,您不会将自引用分配给列表的单个元素]
这是 insert
方法的一个工作示例:
public void insert(int value) {
final Element tmp = new Element(value);
if (this.head == null) { // special case: empty list
tmp.next = tmp; // <-- [D]
this.head = tmp;
this.rear = tmp;
} else { // general case
tmp.next = this.head; // <-- [A]
this.rear.next = tmp; // <-- [B]
this.rear = tmp; // <-- [C]
}
}