时间戳

首页 > 解决方案 > 回文检查抛出无限循环（使用迭代器和链表集合）

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

问题描述

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

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

我究竟做错了什么？

标签： collectionslinked-listiteratorstackinfinite-loop

解决方案

有很多问题：

  • list.size() % 1 == 0不检查大小是否均匀。正确的检查是% 2。
  • 堆栈异常不会发生在您放置该注释的行上。它发生在您拥有的代码的更下方stack.pop()。此异常的原因是您尝试从没有更多元素的堆栈中弹出一个元素。
  • 在您放置该评论的地方不会发生无限循环。它会发生在您在代码中进一步的任何其他循环中：您永远不会调用itr.next()or 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因为继续迭代没有进一步的好处。
  • 该函数不应将堆栈作为参数：您总是希望从一个空堆栈开始，所以这应该是一个局部变量，而不是一个参数。
  • 对Math.ceil已经是int. 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;
}

推荐阅读