206. Reverse Linked List

206. Reverse Linked List

遞迴

1. 如果當前節點沒有下一個節點，有兩種情況

   1. 這個 Linked List 只有一個節點，那返回該節點就是反轉的 Linked List

   2. 這是 Linked List 的「**最後」**一個節點，返回該節點。

2. 如果當前節點有下一個節點，繼續遞迴，遞迴返回的是最後一個節點

3. 遞迴結束，代表當前節點後面的所有節點已經反轉完畢，這時候

   1. 當前節點還是指向原先指向的節點

   2. 將當前節點原先指向的節點指向當前節點

   3. 當前節點指向 None

4. 回傳結尾的節點

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head or not head.next: 
            return head
        last = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return last

迭代

利用兩個指針來記憶節點

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        prev = None
        curr = head
        while curr:
            nxt = curr.next
            curr.next = prev
            prev = curr
            curr = nxt

        return prev