leetcode day 16: reverse a list

Singly-linked list, reverse it.

This is the cycle() function from “two queues as a stack”, but I somehow had some problems getting it right out of the gate.

It’s the same basic thing: if the list is empty, you’re already done. Else, pop a node off the old list, push it onto the new one, return the pointer to the new list.

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    if head == nil {
        return head
    }
    var newhead *ListNode
    var p *ListNode
    for {
        if head == nil {
            break
        }
        p = head        // point to head of current list
        head = head.Next // drop head node from list
        p.Next = newhead // append new list to p
        newhead = p      // save new list
    }
    return newhead
}

Interesting scoring – top 77% CPU, top 66% memory.

Good enough, I think.