还原单链接列表迭代就地

Question

我学习了即将到来的考试，我们有以下运动：

以下规则将其还原为单链接列表：

• 迭代
• 就地
• 没有构造
• 最后一个元素总是null作为下一个元素

我已经找到了一些解决方案，并纷纷拿出自己：

public ListElement<T> revert(ListElement<T> head) 
{ 
    if(head == null) 
    return null; 

    ListElement<T> prev = null; 
    for(ListElement<T> next = head.next(); head.hasNext(); head = next){ 
     head.setNext(prev); 
     prev = head; 
    } 

    return head; 
} 

，但我们的测试框架（只给出了JUnit的反馈）不给我比这更多信息：

Testheadder – testReverseStatic_correct_inplace(singly_linked_list.reverse.test_reverse_iterative.TestReverseList) 

Message – test timed out after 30 milliseconds 

我做错了什么？

在此先感谢！

Answer 1

在您的实现中，next值不会改变：

ListElement<T> prev = null; 
for(ListElement<T> next = head.next(); head.hasNext(); head = next){ 
    head.setNext(prev); 
    prev = head; 
} 

这是一个理想的程序员技能，以便能够调试在纸上这样简单的问题。 练习这一点很重要。 你可以写与变量及其与每一个指令的状态变化，例如表，给出1 -> 2 -> 3 -> null链表的初始状态：

head = 1 -> 2 -> 3 -> null 
prev = null 

的变量将通过与每个指令以下状态：

step    | prev   | head    | next 
start    | null   | 1 -> 2 -> 3 -> null | null 
next = head.next() | null   | 1 -> 2 -> 3 -> null | 2 -> 3 -> null 
head.setNext(prev) | null   | 1 -> null   | 2 -> 3 -> null 
prev = head  | 1 -> null  | 1 -> null   | 2 -> 3 -> null 
head = next  | 1 -> null  | 2 -> 3 -> null  | 2 -> 3 -> null 
head.hasNext() => true 
head.setNext(prev) | 1 -> null  | 2 -> 1 -> null  | 2 -> 1 -> null 
prev = head  | 2 -> 1 -> null | 2 -> 1 -> null  | 2 -> 1 -> null 
head = next  | 2 -> 1 -> null | 2 -> 1 -> null  | 2 -> 1 -> null 
head.hasNext() => true 
head.setNext(prev) | 2 -> 2 -> ... | 2 -> 2 -> ...  | 2 -> 2 -> ... 
prev = head  | 2 -> 2 -> ... | 2 -> 2 -> ...  | 2 -> 2 -> ... 
head = next  | 2 -> 2 -> ... | 2 -> 2 -> ...  | 2 -> 2 -> ... 
head.hasNext() => true 
... 

通过2 -> 2 -> ...我指的是2点到2本身， 一个永无止境的循环。 一旦达到这个周期，我们有一个无限循环， 。 这都是因为next永不改变， 等实现停止进展。

这里是一个可能的解决办法：

public ListElement<T> reverse(ListElement<T> head) { 
    ListElement<T> prev = null; 
    for (ListElement<T> node = head; node != null;) { 
    ListElement<T> next = node.next(); 
    node.setNext(prev); 
    prev = head = node; 
    node = next; 
    } 

    return head; 
}