如何修复此循环链表中的此错误?(并集法)

Question

我想在循环链表中创建一个方法，将两个列表的并集作为参数，但它不起作用，因此我在两个列表中组合了更多的元素，我认为我的逻辑是正确的，但我不知道错在哪里。如果有人能帮我，我将不胜感激。

这是一种方法：

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 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;
}


public boolean isInList(int value) {
if(this.head == null)
return false;

Element cur = this.head;
while(cur != this.rear) {
if(cur.data == value)
return true;
cur = cur.next;
}
return false;
}


@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);
//      Element cur = this.head;
//      Element prev = null;

//special case: empty list
if(this.head == null) {
tmp.next = tmp;
this.head = tmp;
this.rear = tmp;

}else { // general case
//          while (cur != rear && cur.data < value) { //ascending
//               prev = cur;
//               cur = cur.next;
//           }
//           
//           tmp.next = cur;
//           cur.next = tmp;
//      }  
//  }
tmp.next = this.head;
this.rear.next = tmp; 
this.rear = tmp;
}

}


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.rear.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;
}
//          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 static 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) {
Element curA = a.head;
CircularLinkedList c = new CircularLinkedList();

if(a.head == null || b.head == null)
return c;

while(curA != a.rear) {
if(b.isInList(curA.data))
c.insert(curA.data);
curA = curA.next;
}
return c;
}


public boolean isEqualTo(CircularLinkedList a) {  //same content in same order
Element cur = this.head;
Element curA = a.head;

while(cur != this.rear && curA != a.rear) {
if(cur.data != curA.data) {
return false;
}
cur = cur.next;
curA = curA.next;
}
return true;
}


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) {
if(this.head == null)
return -1;

if(!isInList(value))
return -1;

if(this.head.data == this.rear.data)
this.head =null;

Element cur = this.head;
Element prev = null;
Element tmp = null;
int c = 0;
while(cur != this.rear) {
if(cur.next != this.head && cur.next.data == value) {
prev = cur;
tmp = cur.next;
c++;
}
cur = cur.next;
}
return c;
}


public static void main(String[] args) {
CircularLinkedList list = new CircularLinkedList();
CircularLinkedList list1 = new CircularLinkedList();
CircularLinkedList list2 = new CircularLinkedList();

list.insert(8);
list.insert(2);
list.insert(4);
list.insert(3);
list.insert(10);
list.insert(5);
list.insert(8);
list.insert(4);     
System.out.println(list);

//      list2.insert(8);
//      list2.insert(2);
//      list2.insert(4);
//      list2.insert(3);
//      list2.insert(10);
//      list2.insert(5);
//      list2.insert(8);
//      list2.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(4);  // working
//      System.out.println(list);

//      System.out.println(union(list, list1));  //not working

//      System.out.println(list2.inter(list, list1));  //working

//      System.out.println(list.isEqualTo(list1));  // working
}
}

Answer 1

因为使用了do-while循环，所以当在第一个all元素中插入新列表时，第二个和第三个do-whil循环可能会导致问题。我会这样做：

public static CircularLinkedList union(CircularLinkedList a, CircularLinkedList b) {
Element curA = a.head;
Element curB = b.head;
CircularLinkedList c = new CircularLinkedList();
while (!(curA == a.rear && curB == b.rear)) {
if (curA == a.rear) {
c.insert(curB.data);
curB = curB.next;
} else if (curB == b.rear) {
c.insert(curA.data);
curA = curA.next;
} else if (curA.data < curB.data) {
c.insert(curA.data);
curA = curA.next;
} else {
c.insert(curB.data);
curB = curB.next;
}
}
return c;
}

当您开始对您的类合并排序进行gernify时，可能会非常有用。我也会检查重复的。