搜索设置 网站,沈阳今天刚刚发生的新闻,常用的网站制作软件,成都设计公司工作室LeetCode 92. 反转链表 II 给你单链表的头指针 head 和两个整数 left 和 right #xff0c;其中 left right 。请你反转从位置 left 到位置 right 的链表节点#xff0c;返回 反转后的链表 。 示例 1#xff1a; 输入#xff1a;head [1,2,3,4,5], left 2, right 4…LeetCode 92. 反转链表 II 给你单链表的头指针 head 和两个整数 left 和 right 其中 left right 。请你反转从位置 left 到位置 right 的链表节点返回 反转后的链表 。 示例 1 输入head [1,2,3,4,5], left 2, right 4 输出[1,4,3,2,5] 示例 2 输入head [5], left 1, right 1 输出[5] 提示 链表中节点数目为 n 1 n 500 -500 Node.val 500 1 left right n 进阶 你可以使用一趟扫描完成反转吗 # Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# self.val val
# self.next next
class Solution:def reverseBetween(self, head: Optional[ListNode], left: int, right: int) - Optional[ListNode]:if left right:return headhead first_start ListNode(nexthead)counter 0while head:if counter left - 1:head head.nextelif counter left - 1:first_end headhead head.nextelif counter left:second_start headpre headhead head.nextelif counter right:tmp head.nexthead.next prepre headhead tmpelif counter right:second_end headthird_start head.nexthead.next prepre None# 拼接first_end.next second_endsecond_start.next third_startreturn first_start.nextelse:breakcounter 1时间复杂度 O(n)一个大循环最多遍历链表完整一次计O(n)。共O(n)。 空间复杂度 O(1)常量。共 O(1)。
还是官解写的简洁
class Solution:def reverseBetween(self, head: ListNode, left: int, right: int) - ListNode:# 设置 dummyNode 是这一类问题的一般做法dummy_node ListNode(-1)dummy_node.next headpre dummy_nodefor _ in range(left - 1):pre pre.nextcur pre.nextfor _ in range(right - left):next cur.nextcur.next next.nextnext.next pre.nextpre.next nextreturn dummy_node.next# 作者力扣官方题解
# 链接https://leetcode.cn/problems/reverse-linked-list-ii/solutions/634701/fan-zhuan-lian-biao-ii-by-leetcode-solut-teyq/
# 来源力扣LeetCode
# 著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。
