如何在给定头节点的情况下递归地找到链表中最大的项？

Question

int findLargest (ListNode *p)
// --------------------------------------------------------------------------
// Preconditions: list head pointer is passed as a parameter.
// Postconditions: returns the largest value in the linked list.
// --------------------------------------------------------------------------
{
    if (p->item != NULL)
    {
        int largest = p->item;
        if (largest > p->next->item)
            ...
    }

    ...
}

是否可以编写仅传递指针作为参数的递归函数？我不知道如何在不添加更多参数的情况下做到这一点。有什么想法吗？我只使用顺序搜索。没什么花哨的。

这是类 List 中需要的部分：

    struct ListNode 
    {
        ListItemType item;  // A data item on the list.
        ListNode    *next;  // Pointer to next node
    }; // end ListNode

    ListNode   *head; // Pointer to linked list of items.

我主要担心问题的可行性。仅用指针作为参数可以完成此操作吗？

Answer 1

虽然 C 不需要尾递归优化，但如果您可以将其转换为尾递归（并且您不需要在这里做很多工作），那么，当应用该优化时，您可以保持可读性、清晰度和递归的简洁性与最佳非递归解决方案具有相同的性能（时间和空间）。

我稍微修改了函数的条件，以便它可以在没有节点的空列表上工作（其中 p 为 null），并且在这种情况下将返回 null。这是尾递归，并且确实需要另一个参数：

ListNode* findLargestRecurse(ListNode* p, ListNode* largest) {
  // this is an implementation detail, and would not be called directly
  // requires that largest is not null, but p may be null
  if (!p) return largest;
  if (p->item > largest->item) largest = p;
  return findLargestRecurse(p->next, largest);
}

// preconditions: list head pointer is passed as a parameter, and may be null
// postcondition: returns the node with the largest value, or null
ListNode* findLargest(ListNode* p) {
  if (!p) return 0; // mark A, see below
  return findLargestRecurse(p->next, p);
}

请注意，您使用主条目 findLargest 来设置实际递归 findLargestRecurse 的初始条件/上下文。

但是，我会将尾递归编写为迭代 while 循环，以减少对当前编译器特定且在 C 中通常不熟悉的内容的依赖，这并不难做到：

// preconditions: list head pointer is passed as a parameter, and may be null
// postcondition: returns the node with the largest value, or null
ListNode* findLargest(ListNode* p) {
  ListNode* largest = 0;
  for (; p; p = p->next) {
    if (!largest || p->item > largest->item) {
      largest = p;
    }
  }
  return largest;
}

您可以分离出 !largest< /code> 通过预先执行此操作来从循环中获得条件，通过检查基本情况，就像第一个 findLargest 所做的那样（“标记 A”）。

现在看看这个，你可能想知道为什么我称递归版本更简洁：它确实不适合这个简单的例子。这部分是因为 C 的设计有利于迭代（特别注意 for 循环），部分是因为我试图在递归中变得冗长，而不是像通常那样将其压缩（这样你可以更容易地理解它），剩下的就是因为这只是一个简单的问题。

Answer 2

我发现大多数递归问题都可以使用思考框架/模板来解决：

• 我现在手头有哪些信息？
• 如果进行递归调用，我会得到什么信息？
• 我怎样才能将这两者结合起来得到最终结果？
• （另外，一定要清楚“基本情况”。）

在这种情况下，答案是

• 当前节点中的值，即
• 该节点之后的列表“后缀”中的最大元素，
• 嗯，那就是给你的弄清楚
• （对于空列表，你应该返回什么？家庭作业说了？）

玩得开心。 :)

Answer 3

我已经看到一些发布的代码，并且忍不住添加我自己的......因为我真的认为它可以更简单地完成:)

我认为 item 是数字类型。

#include <algorithm> // std::max
#include <limits>    // std::numeric_limits

ListItemType findLargest(const ListNode* p)
{
  if (p == 0)
    return std::numeric_limits<ListItemType>::min();
  else
    return std::max(p->item, findLargest(p->next));
}

正如您所看到的，简单得多，而且我冒昧地添加了一个 const 因为我们当然不需要修改列表本身！

Answer 4

这绝对是可行的，尽管我同意递归不是解决这个问题的最佳方案。在这种情况下，非递归代码将更容易阅读（递归），更快（函数调用的开销），并且内存效率更高（显然有更多的堆栈帧）。

每个递归调用都返回其值或列表其余部分的值中的较大者。

int findLargest (ListNode *p) {
    int current = p->item;
    int next;

    if (p->next == NULL) {
        //The value at this node is obviously larger than a non-existent value
        return current;
    } else {
        //Recur to find the highest value from the rest of the LinkedList
        next = findLargest(p->next);
    }

    //Return the highest value between this node and the end of the list
    if (current > next) {
        return current;
    } else {
        return next;
    }
}

当next 项为空时，递归停止。

Answer 5

Java版本

return max(head, head.value);
int max(Node node, int currentMax)
{
    if(node==null)
        return currentMax;
    if(node.value>currentMax)
        return max(node.next, node.value);
    else
        return max(node.next, currentMax);
}

Answer 6

如果您只想返回最大值，那么您几乎已经写好了。

int FindLargest(ListNode* node){
  if (node != NULL){
    int downTheListLargest = FindLargest(node->next);
    if (downTheListLargest > node->item){
      return downTheListLargest;
    }
    return node->item;
  }
  return //?? some max negative value
}

如果您希望返回指向最大节点的指针，则参数需要是双指针（**），或者函数需要返回指针。

ListNode* FindLargest(ListNode* node){
  if (node == NULL){
    return NULL;
  }
  ListNode* downTheListLargestNode = FindLargest(node->next);
  if (downTheListLargestNode && downTheListLargestNode->item > node->item){
    return downTheListLargestNode;
  }
  return node;
}

实际上没有理由递归地执行此操作。我认为这只是学习递归的练习，但我觉得这是一个糟糕的学习示例。

Answer 7

这是另一个惯用的递归解决方案，类似于 Matthieu 的解决方案。与他的解决方案不同，这个解决方案需要一个空列表 - 可以说，获取空列表中的最小项目并不是一个有意义的操作：

// Precondition: list is non-empty.
int find_largest(ListNode const* n) {
    assert(n != 0 && "find_largest requires non-empty list.");
    return n->next == 0 ? n->item
                        : max(n->item, find_largest(n->next));
}

这个解决方案读起来很像数学定义，使用“cases”符号：

             { item(i),                   if i is the last node
largest(i) = {
             { max{item(i), largest(i+1)} else.

Answer 8

不需要递归，并且您的示例不是递归（它必须调用自身）。

仅使用指针作为参数就可以做到这一点。

提示：将 p 分配给 p->next 以在列表中前进。

Answer 9

始终将递归问题分为两个步骤：停止条件和“问题的其余部分”。首先考虑停止条件。在链表中，它通常是空节点。但就您的情况而言，请考虑当给定节点为空时会发生什么。你会返回什么？事实是，无论如何你都必须返回最大值，并且当列表中没有元素时，就没有 max 元素。在这种情况下，也许您可​​以假设列表必须至少有一个元素。

那么停止条件是什么呢？停止条件是当列表中有单个元素时；在这种情况下，最大值是该节点的值。

下一步是递归步骤。假设您有一个链接到列表的元素。请注意我如何描述链表：链接到链表的节点。如果该节点的最大值大于列表的最大值，则最大值为该节点的值，否则为列表的最大值。