回文检查引发无限循环(使用迭代器和链表集合)

我正在尝试编写一个方法来确定字符串类型的单链表是否是回文。

其思想是将后半部分复制到堆栈中，然后使用迭代器弹出堆栈中的元素，并检查它们是否与从0到大约一半的单链表元素相同。

但是我的迭代器方法抛出了一个无限循环:

public static boolean isPalindrome(LinkedList<String> list, Stack<String> stack ) {
int halfList = (int) Math.ceil(list.size()/2);   // we get half the list size, then round up in case it´s odd
// testing: System.out.println("half of size is " + halfList);`

// copy elements of SLL into the stack (push them in) after reaching the midpoint
int count = 0;
boolean isIt = true;

Iterator<String> itr = list.iterator();  
Iterator<String> itr2 = list.iterator();  

System.out.println("n i print too! ");

// CHECK!! Node head = list.element();

// LOOP: traverse through SLL and add the second half to the stack (push)
// if even # of elements
if ( list.size() % 1 == 0 ) {
System.out.println("n me too! ");
while ( itr.hasNext() ) {
String currentString = itr.next();      // this throws an exception in thread empty stack exception
count ++;
if ( count == halfList ) stack.push(list.element());
// THIS IS THE INFINITE LOOP
System.out.println("n me three! ");
}
}

// else, if odd # of elements
else {
while ( itr.hasNext() ) {
count ++;
if ( count == halfList -1 ) stack.push(list.element());
}
}

// Now we compare the first half of the SLL to the stack (pop off elements)
// even
if ( list.size() % 1 == 0 ) {       
while ( itr2.hasNext() ) {
count ++;
if ( count == halfList +1 ) break;
int compared = stack.pop().compareTo(list.element());
if ( compared != 0) isIt = false;     // if when comparing the two elements, they aren´t similar, palindrome is false
}
}   
// odd
else {
while ( itr2.hasNext() ) {
count ++;
if ( count == halfList ) break;
int compared = stack.pop().compareTo(list.element());
if ( compared != 0) isIt = false;
}
}
return isIt;
}

我做错了什么?

有很多问题:

list.size() % 1 == 0未检查大小是否均匀。正确的检查是% 2
堆栈异常不能发生在您放置注释的行上。它发生在代码的更下面，你有stack.pop()。出现此异常的原因是，您试图从没有其他元素的堆栈中弹出一个元素。
无限循环不会发生在你放置注释的地方。它将出现在代码中的任何其他循环中:在那里您永远不会调用itr.next()或itr2.next()，因此如果您到达那里，您将无限循环。
堆栈被压入的值永远不会超过1个。这是因为您有一个严格的等式条件，该条件在迭代过程中仅为真一次。这不是你想要的:你想要列表的一半最终在堆栈上。这也是为什么你会得到堆栈错误的原因:代码的后半部分期望堆栈上有足够的项。
push(list.element())总是将第一个列表的值压入堆栈，而不是当前迭代的值。应该是push(currentString)。
count ++;被放置在循环中不直观的位置。如果将该行移动到循环中的最后一条语句，则更有意义。
if ( count语句都是错误的。如果将count ++移动到最后一条语句，那么这个if在偶数情况下应该读取if ( count >= halfList )，在奇数情况下应该读取if ( count > halfList )。当然，如果halfList已经被改编，它会更容易，这样你就可以平等地处理奇数和偶数的情况。
代码的第二部分没有重置计数器，而是继续使用count ++。这将使if ( count == halfList )永远不会为真，因此这是stack.pop()最终会引发异常的另一个原因。要么你应该在开始第二部分之前重置计数器(使用count = 0;)，或者，更好的是，你应该检查堆栈是否为空，然后退出循环。
代码的后半部分不需要区分奇数或偶数。
与其将isIt设置为false，不如直接使用return false退出函数，因为继续迭代没有进一步的好处。
函数不应该把堆栈作为参数:你总是想从一个空堆栈开始，所以这应该是一个局部变量，而不是一个参数。

int

Math.ceil

int

(list.size()+1) / 2

在调试代码时，这些问题中的大多数都很明显。在打印行中加上"我在这里"并没有多大帮助。更好的方法是打印变量的值，或者在检查变量的同时，用一个好的调试器逐步检查代码。如果你这样做了，你就会发现上面列出的许多问题。

以下是解决上述问题的代码版本:

public static boolean isPalindrome(LinkedList<String> list) {
Stack<String> stack = new Stack<String>(); 
int halfList = (list.size()+1) / 2; // round upwards
Iterator<String> itr = list.iterator(); 

while (halfList-- > 0) itr.next(); // skip first half of list
while ( itr.hasNext() ) stack.push(itr.next()); // flush rest unto stack
Iterator<String> itr2 = list.iterator();  
while ( itr2.hasNext() && !stack.empty()) { // check that stack is not empty
if (stack.pop().compareTo(itr2.next()) != 0) return false; // no need to continue
}

return true;
}

相关内容

最新更新

热门标签：