链表，递归地向后遍历

Question

我有一个简单的任务要做，我似乎想不出来。在这个预构建函数中，我必须使用给我的骨架函数（不允许更改它返回的内容和参数），将这个列表按相反的顺序排列。

  //----------- helper function
/**
 * cursedReverse( DataNode )
 *     recursively chase list until get to the end.
 *     create new list at the end of the recursion, return
 *     add nodes to the returned list at the end of the list
 *        since you're coming back up, the end will be reversed.
 * @param node DataNode
 * @return DataList
 */
public static DataList cursedReverse( DataNode node )
{
    //////////////////////////////////////////////////////////////
    // 4. traverse "list", recursively
    //++++++++++++++++++++++++++
    /*
   while( node.next() != null ){
       System.out.println("Going down list recursively " + node.data().value );
       return cursedReverse( node.next() );
   }
    if( node.next() == null ){
        System.out.println("At end of the list " + node.data().value );
       // cursedReverse( node );
        //return temp
    }
    */
    DataList d1 = cursedReverse( node );
    if( node.next() == null ) {
        System.out.println(" We have Reached the end of the list ");
    } else if( node != null ){
        System.out.println("NOT NULL");
    }


   // DataList remaining = cursedReverse( node.next() );

    return null;
}

我知道如何递归地完成列表的底部。但它是一个单向链表，这意味着我只能说node.next（）来获取下一个列表。因此，我想不出一种方法可以在数据列表中倒退。

Answer 1

但它是一个单向链表，这意味着我只能说node.next（）把下一张单子拿下来。所以我想不出路了向后向上数据列表。

它不需要双重联系。递归将允许您在堆栈展开时以相反的顺序访问它。

当您进行递归调用时，您将在列表中逐节点（使用next）向下移动，直到到达最后一个节点（列表的末尾）。

一旦到达末尾，您将开始将节点添加到反向列表中（现在您的最后一个节点将成为该列表中的第一个）。

每次通话完成后，您将返回到上一次通话（从中传递next的通话）。这将是上一个节点的位置。将其添加到列表中。

继续这样做，直到你回到头部。

可以说，我不喜欢检查null（if(node != null) {...}）来采取行动。我喜欢使用null节点作为基本情况。所以，我的应该是这样的：

public static DataList cursedReverse( DataNode node ) {
    if (node == null) 
        return new DataList();
    DataList dl = cursedReverse(node.next());
    dl.add(node);
    return dl;
}

第一个调用应该是cursedReverse(head);。

Answer 2

这：

DataList d1 = cursedReverse( node );

显然是错误的。输入cursedReverse时要做的第一件事是调用cursedReverse。那是StackOverflow。

递归有点像归纳法的证明。它有三个主要部分。

1. 确保存在递归将停止并展开的状态
2. 确保递归一直持续到停止
3. 确保您最终达到状态1

您违反了规则1和3。

很明显，你违反了1规则。

您没有向cursedReverse传递不同的参数，从而破坏了规则3。像这样的事情可能是一个很好的方向。

DataList d1 = cursedReverse( node.next() );

要修复1，您需要执行以下操作：

    if (node != null) {
        if (node.next() != null) {
            DataList reversed = cursedReverse(node.next());
            ...
        } else {
            // Last in the list.
        }
    } else {
        // Null node! Hit the end.
    }

即，当你检测到结束时，确保该方法不会做任何事情（或一些琐碎的事情）-不要再次递归。