How to get min and max value from a linked list using recursive function?-CodePudding

I am started learning data structure. Currently I am learning linked list. I have crated a linked list. I want to get the minimum value and the maximum value from the list using recursive function. I can do that using loop but I want to do that recursively. I have written functions for getting minimum and maximum value. But they are returning the first element of the list.

Minimum value function:

int getMin(node *currentNode) {
  int minValue = INT_MAX;
  if (currentNode != NULL) {
    minValue = minValue < currentNode->data ? minValue : currentNode->data;
    getMin(currentNode->next);
  }
  return minValue;
}

Maximum value function:

int getMax(node *currentNode) {
  int maxValue = INT_MIN;
  if (currentNode) {
    maxValue = currentNode->data > maxValue ? currentNode->data : maxValue;
    getMax(currentNode->next);
  }
  return maxValue;
}

My full program:

#include <bits/stdc  .h>

using namespace std;

struct node {
  int data;
  node *next;
} *root;

void append(vector<int> vec) {
  node *currentNode, *tail;
  root = new node();
  root->data = vec[0];
  root->next = NULL;
  tail = root;
  for (vector<int>::iterator i = vec.begin()   1; i < vec.end(); i  ) {
    currentNode = new node();
    currentNode->data = *i;
    currentNode->next = NULL;
    tail->next = currentNode;
    tail = tail->next;
  }
}

void display(node *currentNode) {
  if (currentNode != NULL) {
    cout << currentNode->data << " ";
    display(currentNode->next);
  }
}

int getMin(node *currentNode) {
  int minValue = INT_MAX;
  if (currentNode != NULL) {
    minValue = minValue < currentNode->data ? minValue : currentNode->data;
    getMin(currentNode->next);
  }
  return minValue;
}

int getMax(node *currentNode) {
  int maxValue = INT_MIN;
  if (currentNode) {
    maxValue = currentNode->data > maxValue ? currentNode->data : maxValue;
    getMax(currentNode->next);
  }
  return maxValue;
}

int main() {
  vector<int> vec {5, 7, 3, 4, 6};
  append(vec);
  display(root);
  cout << "\nMin: " << getMin(root) << "\n";
  cout << "Max: " << getMax(root) << "\n";

  return 0;
}

I am getting the first item of the link. Why not returning the minimum and maximum value? How to fix this problem?

CodePudding user response：

The obvious problem is that you call your function recursively, but ignore the return value. This means that only the first item in the list is considered.

int getMin(node *currentNode) {
  int minValue = INT_MAX;
  if (currentNode != NULL) {
    minValue = minValue < currentNode->data ? minValue : currentNode->data;
    getMin(currentNode->next); // the return value here is being ignored.
  }
  return minValue;
}

Here's the correct solution

int getMin(node *currentNode) {
  if (currentNode != NULL) {
    int curr = currentNode->data;
    int rest = getMin(currentNode->next); // don't ignore the return value
    return curr < rest ? curr : rest; // which is less? the current item or
                                      // the minimum item in the rest of the list
  }
  else {
    return INT_MAX;
  }
}