[数据结构与算法]链表篇 206. 反转链表

206. 反转链表(难度 简单)

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

示例 1：

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

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

输入：head = []
输出：[]

提示：

链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

题解：
直接将指针反转过来就行 为了防止反转后断开需要用临时指针

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

递归实现

# 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
        cur=head
        def reverse(prev,cur):
            if not cur :
                return prev
            temp=cur.next
            cur.next=prev
            return reverse(cur,temp)
        return reverse(None,cur)

这道题还挺简单的，就是反转下指针，实现起来也比较容易
时间复杂度o(n)
空间复杂度o(1)