2487. Remove Nodes From Linked List

Description

You are given the head of a linked list.

Remove every node which has a node with a greater value anywhere to the right side of it.

Return the head of the modified linked list.

Examples

Example 1:

Input: head = [5,2,13,3,8]
Output: [13,8]
Explanation: The nodes that should be removed are 5, 2 and 3.

• Node 13 is to the right of node 5.
• Node 13 is to the right of node 2.
• Node 8 is to the right of node 3.

Example 2:

Input: head = [1,1,1,1]
Output: [1,1,1,1]
Explanation: Every node has value 1, so no nodes are removed.

Constraints

• The number of the nodes in the given list is in the range [1, 105].
• 1 <= Node.val <= 105

C/C++

題目要求是他要將現在節點以左的所有小於現在節點的節點刪除，轉念一想，將鍊結串列做倒序再去做遍歷，並希望維持 ascending 的性質，在 return 時再一次倒序回來便是答案。最多需要 3N 的複雜度。

class Solution {
public:
    ListNode* reverse(ListNode* head) {
        ListNode* prev = NULL;
        ListNode* temp;
        while (head != NULL) {
            temp = head->next;
            head->next = prev;
            prev = head;
            head = temp;
        }
        return prev;
    }
    ListNode* removeNodes(ListNode* head) {
        head = reverse(head);
        ListNode* temp = head;
        while (temp->next != NULL) {
            if (temp->next->val < temp->val) {
                temp->next = temp->next->next;
            } else
                temp = temp->next;
        }
        return reverse(head);
    }
};