206 反转链表

题目206 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：
输入：head = [1,2]
输出：[2,1]

示例 3：
输入：head = []
输出：[]

双指针思路：

• 定义指针cur指向head，定义指针pre，定义为None，作为链表的最后节点的指向节点
• 然后开始反转了，定义一个临时指针temp保存cur.next节点，因为反转后cur指针的next指向pre，不在是原先的cur.next节点了，将cur->next 指向pre，此时已经反转了第一个节点了。
• 接下来，就是循环走如下代码逻辑了，继续移动pre和cur指针。
• 最后，cur 指针已经指向了null，循环结束，链表也反转完毕了。 此时我们return pre指针就可以了，pre指针就指向了新的头结点。

注意：本来考虑head和head.next是否为空，最后发现为空也不影响结果。

代码

# 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: Optional[ListNode]) -> Optional[ListNode]:
        # if head != None and head.next != None:
        #     pre = None
        #     cur = head

        #     while cur != None:
        #         temp = cur.next
        #         cur.next = pre

        #         pre = cur
        #         cur = temp
        #     return pre
        # return head

        pre = None
        cur = head

        while cur != None:
            temp = cur.next
            cur.next = pre
            pre = cur
            cur = temp
        return pre

递归思路

建议双指针思路，递归直接不容易写，但是根据双指针代码，可以写出递归代码。

# 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: Optional[ListNode]) -> Optional[ListNode]:
        # pre = None
        # cur = head

        # while cur != None:
        #     temp = cur.next
        #     cur.next = pre
        #     pre = cur
        #     cur = temp
        # return pre

        return self.reverse(None, head)
    def reverse(self, pre, cur):
        while cur != None:
            temp = cur.next
            cur.next = pre
            return self.reverse(cur, temp)
        return pre