Untitled

mail@pastecode.io avatar
unknown
c_cpp
a year ago
1.3 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, do the following:
  while (current != nullptr) {
    // 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();
      }

      // If the stack is empty, then the current node is the head of the longest non-increasing sub-list.
      if (stack.empty()) {
        return current;
      } else {
        // Otherwise, 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;
  }

  return nullptr;
}