java - 链表，向后递归

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() 来获取下一个列表。所以我想不出一种方法来向后移动 DataList。

Answer 1

But its a one way linked list, meaning I can only say node.next() to get the next list on the way down. So I can't think of a way to go backwards up the DataList.

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

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

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

每次调用完成后，您将返回到上一个调用(您从中传递 next 的调用)。这将是前一个节点的位置。将其添加到列表中。

继续这样做，直到您回到领先地位。

我不喜欢检查 null (if(node != 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);。