反轉單連結清單

1. 題目

   輸入一個單連結清單，反轉連結清單後，輸對外連結表的所有元素。

2. 解法

2.1 循環（疊代）

# 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
        """
        prev = None
        curr = head
        while curr:
            temp = curr.next
            curr.next = prev
            prev = curr
            curr = temp
            
        return prev
           

2.2 遞歸

遞歸三定律：

（1）遞歸算法必須有個基本結束條件；

（2）遞歸算法必須改變自己的狀态并向基本結束條件演進；

（3）遞歸算法必須遞歸地調用自身。

# 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
        """
        return self.reverse(head)
    
    def reverse(self, node, prev = None):
        if node == None:            #基本結束條件
            return prev
        else:                       #改變自己的狀态，并向基本結束條件演進
            n = node.next
            node.next = prev
            
        return self.reverse(n,node) #遞歸的調用自身