"""
QUESTION:
Reverse a singly linked list.

Hint:
A linked list can be reversed either iteratively or recursively. Could you implement both?
"""

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    # @param {ListNode} head
    # @return {ListNode}
    def reverseList(self, head):
        tail = None
        while head:
            tmp = head.next
            head.next = tail
            tail = head
            head = tmp
        return tail

    def reverseList_2(self, head):
        def dfs(head,newHead):
            if not head:
                return newHead
            next = head.next
            head.next = newHead
            return dfs(next,head)
        return dfs(head, None)

if __name__ == '__main__':
    print