我正在为一个双向链表数据结构编写一个方法,该结构应该将元素列表从索引 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();
}
}
很抱歉,格式不是最好的,复制和粘贴时发生的。