示例:

輸入: 1->2->3->4->5->NULL

輸出: 5->4->3->2->1->NULL

方法1：三指針?lè)?/p>

設(shè)指針cur指向當(dāng)前節(jié)點(diǎn)，反轉(zhuǎn)指針的過(guò)程是改變當(dāng)前節(jié)點(diǎn)的next指針指向當(dāng)前節(jié)點(diǎn)前一個(gè)結(jié)點(diǎn)，所以同時(shí)需要保存前一個(gè)節(jié)點(diǎn)和下一個(gè)節(jié)點(diǎn)，設(shè)指針pre指向當(dāng)前節(jié)點(diǎn)前一個(gè)節(jié)點(diǎn)，指針next指向當(dāng)前節(jié)點(diǎn)下一個(gè)節(jié)點(diǎn)。cur指針最初指向鏈表首節(jié)點(diǎn)，next指向cur下一個(gè)節(jié)點(diǎn)，pre為空，改變當(dāng)前節(jié)點(diǎn)的next結(jié)點(diǎn)指向pre指向的結(jié)點(diǎn)，每這樣操作一次，三個(gè)指針同時(shí)前進(jìn)，直到鏈表尾部為止。最后，返回反轉(zhuǎn)后的鏈表表頭指針。

時(shí)間復(fù)雜度：O(n)

空間復(fù)雜度：O(1)

class Solution:

? ? def reverseList(self, head: ListNode) -> ListNode:

? ? ? ? pre = None

? ? ? ? cur = head

? ? ? ? nex = None

? ? ? ? while cur:

? ? ? ? ? ? nex = cur.next

? ? ? ? ? ? cur.next = pre

? ? ? ? ? ?

? ? ? ? ? ? pre = cur

? ? ? ? ? ? cur = nex

? ? ? ? return pre