回文检查抛出无限循环（使用迭代器和链表集合）

Question

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

想法是将后半部分复制到堆栈中，然后使用迭代器弹出堆栈中的元素并检查它们是否与单链表从 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;
}

我做错了什么？

Answer 1

有很多问题：

list.size() % 1 == 0 没有检查大小是否均匀。正确的检查是 % 2.
堆栈异常不能发生在您放置该注释的行上。它发生在您拥有 stack.pop() 的代码的更下方。此异常的原因是您尝试从没有更多元素的堆栈中弹出一个元素。
无限循环不会发生在您放置该评论的地方。它会出现在代码中进一步的任何其他循环中：在那里你永远不会调用 itr.next() 或 itr2.next()，因此你将无限循环如果你到达那里。
堆栈永远不会被推送超过 1 个值。这是因为你有一个严格的相等条件，在迭代期间只为真一次。这不是您想要的：您希望列表的一半最终进入堆栈。这也是您收到堆栈错误的原因：代码的后半部分期望堆栈中有足够的项目。
push(list.element()) 总是将 first 列表值推入堆栈，而不是当前迭代的值。这应该是 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 时，除法结果为 int。所以要向上取整，除法前加 1：(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;
}

回文检查抛出无限循环（使用迭代器和链表集合）

Palindrome check throws infinite loop (using iterator and linked lists collection)

collections

stack

iterator

linked-list

infinite-loop