'''
 Reverse Linked List

Reverse a singly linked list.

Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

Follow up:

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

'''
#!/usr/python/bin
# _*_ coding=utf-8 _*_
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    '''
    链表倒置的是将链表从尾到头逆转过来。
    
    [description]
    '''
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head is None:
            return []
        temp = head
        newListLast = None
        while temp is not None:
            temp_next = temp.next
            temp.next = newListLast
            newListLast = temp
            temp = temp_next
        retList = []
        newListStart = newListLast
        while newListStart is not None:
            print newListStart.val
            retList.append(newListStart.val)
            newListStart = newListStart.next
        return retList
