Untitled
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; }