2487. 从链表中移除节点

2487. 从链表中移除节点

• 难度: medium
• 原始链接: https://leetcode.cn/problems/remove-nodes-from-linked-list
• 标签: 递归, 单调栈, 反转链表

解法一: 递归

go

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNodes(head *ListNode) *ListNode {
    if head == nil {
        return nil
    }
    next := removeNodes(head.Next)
    if next == nil || head.Val >= next.Val {
        head.Next = next
        return head
    }
    return next
}

解法二: 单调栈

go

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNodes(head *ListNode) *ListNode {
    stack := []*ListNode{}
    node := head
    for node != nil {
        stack = append(stack, node)
        node = node.Next
    }
    pre := -1
    p := &ListNode{
        Val: -1,
        Next: nil,
    }
    for len(stack) > 0 {
        node = stack[len(stack) - 1]
        if node.Val >= pre {
            pre = node.Val
            tmp := p.Next
            p.Next = node
            p.Next.Next = tmp
        }
        stack = stack[:len(stack) - 1]
    }
    return p.Next
}

解法三: 反转链表

go

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNodes(head *ListNode) *ListNode {
    revertHead := revertLinkNode(head)
    node := revertHead
    p := &ListNode{
        Val: -1,
        Next: nil,
    }
    pre := p
    for node != nil {
        if pre.Val <= node.Val {
            pre.Next = node
            node = node.Next
            pre = pre.Next
            pre.Next = nil
        } else {
            node = node.Next
        }
    }
    return revertLinkNode(p.Next)
}

func revertLinkNode(head *ListNode) *ListNode {
    p := &ListNode{
        Val: -1,
        Next: nil,
    }
    node := head
    for node != nil {
        tmp := p.Next
        p.Next = node
        node = node.Next
        p.Next.Next = tmp
    }
    return p.Next
}