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

1# Reverse a singly linked list.
2#
3# Example:
4#
5# Input: 1->2->3->4->5->NULL
6# Output: 5->4->3->2->1->NULL
7#
8# Follow up:
9#
10# A linked list can be reversed either iteratively or recursively. Could you implement both?
11
12# Definition for singly-linked list.
13# class ListNode:
14#     def __init__(self, x):
15#         self.val = x
16#         self.next = None
17
18class ListNode:
19    def __init__(self, x):
20        self.val = x
21        self.next = None
22
23
24# 迭代法
25class SolutionIteratively:
26    def reverseList(self, head):
27        """
28        :type head: ListNode
29        :rtype: ListNode
30        """
31        pre_node = None
32        while head is not None:
33            pre_node, head.next, head = head, pre_node, head.next
34        return pre_node
35
36
37# 递归法
38class SolutionRecursively:
39    def reverseTail(self, cur, pre=None):
40        if not cur:
41            return pre
42        temp_node = cur.next
43        cur.next = pre
44        return self.reverseTail(temp_node, cur)
45
46    def reverseList(self, head):
47        """
48        :type head: ListNode
49        :rtype: ListNode
50        """
51        return self.reverseTail(head)
52
53
54node_5 = ListNode(5)
55node_4 = ListNode(4)
56node_4.next = node_5
57node_3 = ListNode(3)
58node_3.next = node_4
59node_2 = ListNode(2)
60node_2.next = node_3
61node_1 = ListNode(1)
62node_1.next = node_2
63
64solution = SolutionIteratively()
65result = solution.reverseList(node_1)
66print(result)
67
68result_rec = SolutionRecursively().reverseList(node_5)
69print(result_rec)
70