import Foundation

class For16Solution {
    func reversedListNode(_ head: ListNode?) -> ListNode? {
        if head == nil || head?.next == nil {
            return head
        }
        
        var pre : ListNode?
        var cur = head
        pre = nil

        while cur != nil {
            let tmp = cur?.next
            cur?.next = pre
            pre = cur
            cur = tmp
        }
        
        
        head?.next = nil
        
        return pre
    }
    
    func reversedListNode2(_ head: ListNode?) -> ListNode? {

        if head == nil || head?.next == nil {
            return nil
        }
        
        let newHead = reversedListNode2(head?.next)
        head?.next?.next = head
        head?.next = nil
        
        return newHead
    }
}