206. Reversed Linked List

Given the head of a singly linked list, reverse the list, and return the reversed list.

\

Solution 1: Iterative:

• 用双指针的做法
• 一个curr，一个prev，初始值为head和null
• 提前把next node存好
• 然后把curr的next改为prev
• 然后更新curr和prev为原next和curr
• 终止条件是curr为空时，返回prev

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev, curr = None, head
        while curr:
            temp = curr.next
            curr.next = prev
            prev, curr = curr, temp
        return prev

\

Solution 2: recursive:

• 在这里我们想考虑两件事
• 更新next的方法就是将一个node的next的next设置为它自己
• 对于每个node和他的子问题，我们只需要把子问题的尾巴（子问题更新后指向null的最后那个node）指向当前node，然后把node指向null
• 另外我们需要得到一个最新的newHead（通过递归得到）

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return None
        
        newHead = head
        if head.next:
            newHead = self.reverseList(head.next) #保证更新到最末尾的node
            head.next.next = head
        head.next = None

        return newHead

21. Merge Two Linked List