Reverse a singly linked list.

Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

题意

翻转单链表

思路

1. 非递归
   head：记录原链表
   nex：记录原链表头结点的下一个结点
   head和当前head.next断开，head.next指向新链表的头结点new_head，new_head移动到head，head继续遍历原链表，指向原head.next -> nex。

class Solution:
    def reverseList1(self, head: ListNode) -> ListNode:
        new_head = None
        while head is not None:
            nex = head.next
            head.next = new_head
            new_head = head
            head = nex
        return new_head

2. 递归
   我的理解是在遍历到最后一个结点的过程中，实现了两两结点指向的翻转，到走到最后一个结点，前面的已经翻转好，直接返回一个新的链表。

    def reverseList2(self, head: ListNode) -> ListNode:
        if head is None or head.next is None:
            return head
        else:
            #获取到反转后的新的头结点，不管具体内容，把整个从head->next看做一个整体
            new_head = self.reverseList2(head.next)
            # 将当前head指向的那个节点的下一个节点的下一个节点指向head，就把head和head.next的方向换过来了。
            head.next.next = head
            #然后把它自己本身的head.next设置为null，就好了。
            head.next = None
        return new_head