Java递归方法结束但不终止

Question

我正在为双链表数据结构编写一个方法，该数据结构应该按照参数中的指定将索引 a 到 b 的元素列表反转，并决定以递归方式执行此操作。作业的目的是使用节点练习指针操作。我的方法的逻辑对我来说似乎没问题，但是当我通过 JUnit 测试运行代码时它不会结束。觉得这很奇怪，我添加了 println 语句以查看它到达了代码的哪些部分；检查一切正常。所以我通过 Eclipse 的调试器运行它，它到达了结束括号，在所有递归调用来回移动之后，没有终止。它只是坐在最后的支架上，我以前从未见过这样的东西。为什么会这样？我该如何解决？

代码如下:

public void reverseList(int start, int end)
{
    if (start >= end)
    {
        return;
    }

    ListNode left = getListNode(start);
    ListNode right = getListNode(end);
    ListNode leftNext = left.next;
    ListNode leftPrev = left.previous;
    ListNode rightNext = right.next;
    ListNode rightPrev = right.previous;

    leftPrev.next = right;
    rightPrev.next = left;
    leftNext.previous = right;
    rightNext.previous = left;
    left.next = rightNext;
    left.previous = rightPrev;
    right.next = leftNext;
    right.previous = leftPrev;

    reverseList(start + 1, end - 1);
}

编辑:这是测试它的代码

JUnit:

@Test
public void testReveseList()
{
StudentList list = new StudentList();
list.add("a", "");
list.add("b", "");
list.add("c", "");
list.add("d", "");
list.add("e", "");
list.add("f", "");
list.add("g", "");
list.add("h", "");
list.add("i", "");
list.add("j", "");
list.printlist();
list.reverseList(2, 5);
System.out.println();
StudentList expectedList = new StudentList();
expectedList.add("a", "");
expectedList.add("b", "");
expectedList.add("f", "");
expectedList.add("e", "");
expectedList.add("d", "");
expectedList.add("c", "");
expectedList.add("g", "");
expectedList.add("h", "");
expectedList.add("i", "");
expectedList.add("j", "");
assertEquals(expectedList, list);
list.reverseList(2, 5);

System.out.println();

StudentList expectedList1 = new StudentList();
expectedList1.add("a", "");
expectedList1.add("b", "");
expectedList1.add("c", "");
expectedList1.add("d", "");
expectedList1.add("e", "");
expectedList1.add("f", "");
expectedList1.add("g", "");
expectedList1.add("h", "");
expectedList1.add("i", "");
expectedList1.add("j", "");
assertEquals(expectedList1, list);
list.reverseList(0, 9);
System.out.println();
StudentList expectedList2 = new StudentList();
expectedList2.add("j", "");
expectedList2.add("i", "");
expectedList2.add("h", "");
expectedList2.add("g", "");
expectedList2.add("f", "");
expectedList2.add("e", "");
expectedList2.add("d", "");
expectedList2.add("c", "");
expectedList2.add("b", "");
expectedList2.add("a", "");
assertEquals(expectedList2, list);

}

测试类:

public class StudentList
{
private ListNode head = null;

public void add(StudentData data)
{
    ListNode newNode = new ListNode(data);
    ListNode lastNode = getTail();

    if (lastNode == null)
    {
        head = newNode;
    }
    else
    {
        lastNode.next = newNode;
    }

    newNode.previous = lastNode;
    newNode.next = null;

}       

    public ListNode getListNode(int indexOfDesiredNode)
{
    if (indexOfDesiredNode >= size())
    {
        // --- Error: There aren't that many nodes
        return null;
    }

    // --- Move through the list, node by node, until we find
    // --- the one we want
    int count = 0;
    ListNode current = head;
    while ((count < indexOfDesiredNode) && (null != current))
    {
        current = current.next;
        count = count + 1;
    }

    // --- So, did we find anything?
    if (null == current)
    {
        // --- Error: We didn't find the node
        return null;
    }

    return current;
}

    public int size()
{
    if (null == head)
    {
        return 0;
    }

    int count = 0;
    ListNode current = head;
    while (current != null)
    {
        count = count + 1;
        current = current.next;
    }
    return count;
}

    public void reverseList(int start, int end)
{
    if (start >= end)
    {
        return;
    }

    ListNode left = getListNode(start);
    ListNode right = getListNode(end);
    ListNode leftNext = left.next;
    ListNode leftPrev = left.previous;
    ListNode rightNext = right.next;
    ListNode rightPrev = right.previous;

    leftPrev.next = right;
    rightPrev.next = left;
    leftNext.previous = right;
    rightNext.previous = left;
    left.next = rightNext;
    left.previous = rightPrev;
    right.next = leftNext;
    right.previous = leftPrev;

    //-- The easy way of doing it... *sigh*
    // StudentData temp = get(start);
    // getListNode(start).data = getListNode(end).data;
    // getListNode(end).data = temp;

    reverseList(start + 1, end - 1);
}
}

和 ListNode 类:

public class ListNode
{
public StudentData data = null;
public ListNode next = null;
public ListNode previous = null;

public ListNode(StudentData data)
{
    this.data = data;
}

@Override
public String toString()
{
    return data.toString();
}
}

很抱歉，格式不是最好的，这是通过复制和粘贴发生的。

Answer 1

问题出在 end == start + 1 的情况下，因此 rightPrev == left。然后设置 rightPrev.next = left 使列表循环，因此 getListNode 不会终止。