reorder-list.go

// https://leetcode.com/problems/reorder-list

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reorderList(head *ListNode)  {
    var prev *ListNode
    stack := []*ListNode{}
    
    for head != nil {
        stack = append(stack, head)
        head = head.Next
    }
    
    for len(stack) > 0 {
        parent := stack[0]
        stack = stack[1:]
        
        if prev != nil {
            prev.Next = parent
        }
        
        if len(stack) > 0 {
            child := stack[len(stack) - 1]
            stack = stack[:len(stack) - 1]
            
            parent.Next = child
            prev = child
            prev.Next = nil
        } else {
            parent.Next = nil
        }
    }
}