143.go

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reorderList(p *ListNode)  {
    q := findMid(p)
    q = reverse(q)
    zip(p, q)
}

func findMid(p *ListNode) *ListNode {
    q := p
    for q.Next != nil && q.Next.Next != nil {
        p = p.Next
        q = q.Next.Next
    }
    return p
}

func reverse(p *ListNode) *ListNode {
    if p == nil {
        return nil
    }
    q := p.Next
    p.Next = nil
    for q != nil {
        r := q.Next
        q.Next = p
        p, q = q, r
    }
    return p
}

func zip(p, q *ListNode) {
    for p != nil && p != q {
        pp := p.Next
        qq := q.Next
        p.Next = q
        q.Next = pp
        p, q = pp, qq
    }
}