leetcode206 Reverse Linked List

 1 """
 2 Reverse a singly linked list.
 3 Example:
 4 Input: 1->2->3->4->5->NULL
 5 Output: 5->4->3->2->1->NULL
 6 """
 7 
 8 """
 9 两种解法
10 解法一：迭代法
11 是先申请一个pre = None 作为尾结点
12 cur = head 作为当前结点，end = cur.next用来存储下一个需要更新的cur的位置
13 让当前的cur结点与pre相连cur.next = pre，并更新pre = cur, cur = end
14 返回pre
15 """
16 
17 class ListNode:
18     def __init__(self, x):
19         self.val = x
20         self.next = None
21 
22 class Solution1:
23     def reverseList(self, head):
24         pre = None
25         cur = head
26         while cur:
27             end = cur.next
28             cur.next = pre
29             pre = cur
30             cur = end
31         return pre
32 
33 """
34 解法二：递归
35 递归的思想：如果要倒转的链表有n个节点，
36 那么如果第一个节点后面的n-1个节点已经正确倒转了的话，
37 只要处理第一个和第二个节点的指向关系就可以了。
38 要使后面n-1个节点正确倒转，那么闲要使得后面的n-2个节点正确倒转。于是接这么递归下去。
39 最后只剩一个节点的时候，就什么都不用做了，只需要改变其与原来的上一个节点之间的关系就可以了。
40 """
41 class Solution2:
42     def reverse(self, head):
43         if head.next == None:
44             return head
45         p = self.reverse(head.next)
46         head.next.next = head
47         head.next = None
48         return p