題目描述
定義一個(gè)函數(shù)裳涛，輸入一個(gè)鏈表的頭節(jié)點(diǎn)，反轉(zhuǎn)該鏈表并輸出反轉(zhuǎn)后鏈表的頭節(jié)點(diǎn)炬藤。
示例
示例 1：
輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL
限制：
0 <= 節(jié)點(diǎn)個(gè)數(shù) <= 5000
解答方法
方法一：雙指針?lè)?/h2>
思路
定義兩個(gè)指針： pre 和 ccur 晾捏；pre 在前 cur 在后。
每次讓 cur的 next 指向pre穿撮，實(shí)現(xiàn)一次局部反轉(zhuǎn)
局部反轉(zhuǎn)完成之后缺脉， pre和 cur同時(shí)往前移動(dòng)一個(gè)位置
循環(huán)上述過(guò)程，直至pre到達(dá)鏈表尾部
代碼
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
pre = None
cur = head
while cur:
tmp = cur.next
cur.next = pre
pre = cur
cur = tmp
return pre
時(shí)間復(fù)雜度
O(n)
空間復(fù)雜度
O(1)
方法二：遞歸
思路
使用遞歸函數(shù)悦穿，一直遞歸到鏈表的最后一個(gè)結(jié)點(diǎn)攻礼，該結(jié)點(diǎn)就是反轉(zhuǎn)后的頭結(jié)點(diǎn)，記作 ret .
此后栗柒，每次函數(shù)在返回的過(guò)程中礁扮，讓當(dāng)前結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)的 next 指針指向當(dāng)前節(jié)點(diǎn)。
同時(shí)讓當(dāng)前結(jié)點(diǎn)的 next指針指向 NULL 瞬沦，從而實(shí)現(xiàn)從鏈表尾部開(kāi)始的局部反轉(zhuǎn)
當(dāng)遞歸函數(shù)全部出棧后太伊，鏈表反轉(zhuǎn)完成。
代碼
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
if head == None or head.next == None:
return head
ret = self.reverseList(head.next)
head.next.next = head
head.next = None
return ret
