问题

给出一个以头节点 head 作为第一个节点的链表。链表中的节点分别编号为：node1, node2, node_3, ... 。 每个节点都可能有下一个更大值，对于 nodei,其 nextlarger(nodei) 是 nodej.val,那么就有 j > i,且nodej.val > nodei.val,而 j 是可能的选项中最小的那个,如果不存在这样的 j，那么下一个更大值为 0 。 返回整数答案数组 answer，其中 answer[i] = nextlarger(node{i+1}) 。 注意：在下面的示例中，诸如 [2,1,5] 这样的输入（不是输出）是链表的序列化表示，其头节点的值为 2，第二个节点值为 1，第三个节点值为 5

示例

输入：[2,1,5] 输出：[5,5,0] 输入：[2,7,4,3,5] 输出：[7,0,5,5,0]

在看解法之前，请大家先思考下，自己该怎么解决呢

解法一

• 笨办法，将链表转换为数组，双重for循环，依次找到每个元素的的下一个更大值，然后存储到数组，最后转化为链表返回。

解法二

• 遍历链表，将第一个元素入栈，第二元素和已入栈的元素比较，如果大于则将已入栈的元素弹出，将当前元素放入新链表的尾节点，继续和栈中的元素比较，还是大于的话，则将当前元素再放入新链表的尾节点，直到栈中没有元素或者碰到当前元素小于栈中的元素，则将当前元素放入栈中，继续循环，下面画张图来理解一下，光看文字理解起来比较费劲，如下图

• 代码实现：代码是没法运行的，因为GoLang没有内置的栈数据结构

type ListNode struct {
     Val int
     Next *ListNode
}
func nextLargerNodes(head *ListNode) []int {
    result := make([]int,0)
    //创建一个栈（这个栈是虚拟的，GoLang中没有内置的栈数据结构）
    s := new(Stack)
    //将首节点值放入
    s.Push(head.Val)
    temp = head.Next
    index := 0
    //从第二节点遍历链表
    for temp != nil{
       index ++
       for s.IsNotEmpty(){
            v := s.Pop()
            //如果小于栈中的值就放入栈中
            if temp.Val < v{
                s.Push(temp.Val)
                result = append(result,0)
                break
            }else{
                //否则，将当前元素放入返回的结果中
                index -- 
                result[index] = temp.Val
            }
       }
       temp = temp.Next
    }
    //针对链表的最后一个元素补0
    result = append(result,0)
    return result
}

解法三

• 先声明两个切片status（存储链表的值),result(存储下一个节点比当前节点大的值）,for循环链表，将链表的节点的值放入status中，同时比较下一个节点的值是否比当前节点的值，如果大于，将下一个节点的值添加result中，否则给result加0，最后循环result节点，发现不为0的值时往前倒退，看看status中是否有比它更小的值，如果有则将这个不为0的值放入result这个下标处。

func nextLargerNodes(head *ListNode) []int {
    if head == nil{
        return nil
    } 
    status := make([]int,0)
    result := make([]int,0)
    for head.Next != nil{
        status = append(status,head.Val)     
        if head.Next.Val > head.Val{
            result = append(result,head.Next.Val)
        }else{
            result = append(result,0)
        }
        head = head.Next
    }
    //把末尾数据补进来
    result = append(result,0)
    status = append(status,head.Val)
    //遍历result
    for i,v := range result{
        //下标为0的不参与
        if i==0{
            continue
        }
        //当值不为0时，用当前值和链表之前的数据比较，看看
        //是否有小于当前的值,如果小的话，就把result中为0的替换
        if v !=0{
            for temp := i-1;temp>=0;temp--{
                if v <= status[temp]{
                    continue
                }
                if result[temp] == 0{
                    result[temp] = v
                }
            }
        }
    }
    return result
}

欢迎大家关注微信公众号：“golang那点事”，更多精彩期待你的到来