題目：反轉(zhuǎn)鏈表，LeetCode206
要求用循環(huán)和遞歸兩種方法。
一、循環(huán)解法
設(shè)置兩個(gè)外部引用，從前到后的，不斷地反轉(zhuǎn)每個(gè)節(jié)點(diǎn)的指針即可。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
previous = None
current = head
#先獲得current的下一個(gè)node，此時(shí)就有三個(gè)node了
#把current指針指向previous
#再把previous賦值為current
#再把current賦值為下一個(gè)node
while current != None:
next_node = current.next
current.next = previous
previous = current
current = next_node
return previous
二、遞歸解法：
對遞歸了解還不深，需要結(jié)合劍指offer，Python數(shù)算兩本書，再加深理解一下。這里只是暫時(shí)的對代碼做一下解釋。
代碼思想：
- 1、遞歸是層層調(diào)用的，所以注意在self.reverseList函數(shù)調(diào)用到最后一個(gè)節(jié)點(diǎn)，結(jié)束所有的調(diào)用之前，每一步中的下面兩句代碼curr.next.next和curr.next是不會執(zhí)行的。
- 2、一路調(diào)用函數(shù)到最深，然后從最后一個(gè)節(jié)點(diǎn)開始，反轉(zhuǎn)節(jié)點(diǎn)的指針 ，不斷返回上一個(gè)調(diào)用， 也不斷反轉(zhuǎn)上一個(gè)指針，一直到最終的讓舊鏈表的頭結(jié)點(diǎn)指向None。
class Solution:
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
curr = head
#第一個(gè)比較條件，是對特殊輸入None的保證
if curr == None or curr.next ==None:
return curr
newhead = self.reverseList(curr.next)
#這一步更改節(jié)點(diǎn)指針，第一個(gè)next是對curr下一個(gè)節(jié)點(diǎn)的索引，第二個(gè)next才是更改指針操作
curr.next.next = curr
curr.next = None
return newhead
代碼在Example中執(zhí)行的結(jié)果：
- 調(diào)用到curr=5，所有調(diào)用結(jié)束，新的鏈表頭就是節(jié)點(diǎn)5，這也是最終函數(shù)要返回的新的頭結(jié)點(diǎn)
- 所有調(diào)用結(jié)束以后，開始從深到淺的依次執(zhí)行下面兩句代碼。具體化就是：
curr = 4，4.next.next = 4 的意思可以分兩步4.next=5, 5.next = 4，最終結(jié)果就是節(jié)點(diǎn)5的指針指向4。然后4的指針指向None，再返回上一個(gè)調(diào)用
（此時(shí)，1->2->3->4并且5->4->None）
curr = 3，3.next.next = 3 即4的指針指向3,3的指針指向None，再返回上一個(gè)調(diào)用
（此時(shí)，1->2->3并且5->4->3->None）
不斷返回上一個(gè)調(diào)用，最終得到反轉(zhuǎn) 的列表，并且返回newhead=5
