2487. Remove Nodes From Linked List - Medium

前往題目

思路

1. 反轉list
2. 疊代所有元素，並紀錄最大值，小於最大值的話直接移除(略過)
3. 再次反轉

Code

class Solution {
    public ListNode removeNodes(ListNode head) {
        
        // Reverse the list
        head = reverse(head);
        
        ListNode cur = head;
        int max = cur.val;
        // Iterate in reversed order
        while (cur.next != null) {
            // Update max value
            max = Math.max(max, cur.val);
            if (max > cur.next.val) {
                // Skip the next node
                cur.next = cur.next.next;
            } else {
                // Actually move the pointer
                cur = cur.next;
            }
        }
        // Reverse again
        return reverse(head);
    }

    private ListNode reverse(ListNode head) {
        ListNode prev = null;

        // Reverse the list
        while (head != null) {
            ListNode next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        
        return prev;
    }
}