• 分類：LinkedList
• 時間復雜度: O(n)
• 空間復雜度: 迭代:O(1),遞歸O(n)

206. Reverse Linked List

反轉(zhuǎn)一個單鏈表。

示例:

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

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

你可以迭代或遞歸地反轉(zhuǎn)鏈表。你能否用兩種方法解決這道題？

來源：力扣（LeetCode）

鏈接：https://leetcode-cn.com/problems/reverse-linked-list

著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

代碼1：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def helper(self, res, head):
        if head == None:
            return res

        tmp = head.next
        head.next = res
        return self.helper(head,tmp)

    def reverseList(self, head: ListNode) -> ListNode:
        res = None
        if head == None:
            return res
        
        return self.helper(res,head)

代碼2：

# 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:
        res = None
        if head == None:
            return res
        
        pointer = head
        while(pointer!=None):
            tmp = pointer.next
            pointer.next = res
            res = pointer
            pointer = tmp
        
        return res

討論：

1.迭代和遞歸兩種方法，b站上的大圣講題講的很清楚，而且比較簡短，建議一聽