手机网站功能,建设网站作用,成都建设网站哪家好,详情页模板软件题目
给你单链表的头节点 head #xff0c;请你反转链表#xff0c;并返回反转后的链表。
示例 1#xff1a; 输入#xff1a;head [1,2,3,4,5] 输出#xff1a;[5,4,3,2,1]
示例 2#xff1a; 输入#xff1a;head [1,2] 输出#xff1a;[2,1]
示例 3#xff1…题目
给你单链表的头节点 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
题目链接
我的思路
定义cur指向当前节点pre指向倒序链表每次将当前节点的next指向pre 重点是每次要记录cur原来的next节点否则就找不到了
我的代码
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# self.val val
# self.next next
class Solution:def reverseList(self, head: Optional[ListNode]) - Optional[ListNode]:pre Nonecur headwhile cur:tmp cur.nextcur.next prepre curcur tmp return pre注意最后要返回pre而不是cur
题解思路
这道题还可以用递归做
把原问题转化成解决第一个节点怎么翻转的问题不考虑里面的节点 递归过程
head是我们要进行翻转的节点head.next是已经翻转好的剩余节点那么只需要把剩余节点的next指向head即head.next.nexthead如果head是最后一个节点那么要把head.next置为None
终止条件如果只有一个节点就返回那个节点
参考代码
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# self.val val
# self.next next
class Solution:def reverseList(self, head: Optional[ListNode]) - Optional[ListNode]:if not head or not head.next: return headtmp self.reverseList(head.next)head.next.next headhead.next Nonereturn tmp
ps
链表类题目先画图理解再做题更好做
