Untitled
c_cpp
a month ago
1.4 kB
1
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(); } }