LeetCode-2487 从链表中移除节点

Table of Contents

LeetCode-2487 从链表中移除节点 #

Solution 1 #

递归. 函数处理完的状态是返回一个节点, 这个节点已经是原链表中最大的节点. 我们将头节点与右侧处理完返回的节点的值比较即可.

class Solution:
    def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None:
            return None
        head.next = self.removeNodes(head.next)
        if head.next is not None and head.val < head.next.val:
            return head.next
        return head

Solution 2 #

用栈来模拟递归.

class Solution:
    def removeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
        st = []
        while head is not None:
            st.append(head)
            head = head.next
        while st:
            if head is None or st[-1].val >= head.val:
                st[-1].next = head
                head = st[-1]
            st.pop()
        return head