Untitled

mail@pastecode.io avatar
unknown
c_cpp
a year ago
1.4 kB
2
Indexable
Never
SinglyLinkedListNode* findLongestList(SinglyLinkedListNode* head) {
  // Create a stack to store the nodes of the longest non-increasing sub-list.
  stack<SinglyLinkedListNode*> stack;

  // Initialize the current node to the head of the linked list.
  SinglyLinkedListNode* current = head;

  // While the current node is not null and the stack is not empty, do the following:
  while (current != nullptr && !stack.empty()) {
    // If the current node is greater than or equal to the top of the stack, then push it to the stack.
    if (current->data >= stack.top()->data) {
      stack.push(current);
    } else {
      // Otherwise, the current node cannot be part of the longest non-increasing sub-list.
      // Pop all the nodes from the stack that are smaller than the current node.
      while (!stack.empty() && stack.top()->data < current->data) {
        stack.pop();
      }

      // The next node in the stack is the head of the longest non-increasing sub-list.
      current = stack.top();
    }

    // Move on to the next node.
    current = current->next;
  }

  // If the stack is empty, then there is no non-increasing sub-list.
  if (stack.empty()) {
    return nullptr;
  } else {
    // Otherwise, the top of the stack is the head of the longest non-increasing sub-list.
    return stack.top();
  }
}