微网站开发外包,商城网站欣赏,湖南最新消息今天,常州做的网站的公司文章目录 Tag题目来源题目解读解题思路方法一#xff1a;迭代 其他语言python3 写在最后 Tag
【头插法】【迭代】【链表】 题目来源
92. 反转链表 II 题目解读
返回部分链表。 解题思路
方法一#xff1a;迭代
我们首先需要找到开始反转链表的前一个节点#xff0c;为此… 文章目录 Tag题目来源题目解读解题思路方法一迭代 其他语言python3 写在最后 Tag
【头插法】【迭代】【链表】 题目来源
92. 反转链表 II 题目解读
返回部分链表。 解题思路
方法一迭代
我们首先需要找到开始反转链表的前一个节点为此我们设计一个哑结点 dummy并且哑结点指向头结点。接着通过 left 次循环得到开始反转链表的前一个节点 prev。
使用头插法来反转部分链表当然也可以使用 206. 反转链表 中的反转方法但是不仅需要找到 prevNode 节点还要找到 right 后面的第一个节点这样就需要遍历两次链表。二接下来介绍的头插法只需要一次遍历。
整体思想是在需要反转的区间里每遍历一个节点就将这个节点放置到反转部分的起始位置。为此需要几个变量
prevNode指向的是待反转区域第一个节点 left 的前一个节点也就是实现通过 for 循环求出来的那个节点currNode指向反转区域的当前遍历的节点nextNode指向反转区域的当前遍历的节点的下一个节点。
接下来通过一个例子的图解来说明头插法是如何实现反转部分链表的。 遍历反转区域的每一个节点按照图示的方法迭代即可完成部分节点的反转。对于链表类的题目快速画出一个示意图按照图示的指针指向关系来写代码可以避免很多错误。
实现代码
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* reverseBetween(ListNode* head, int left, int right) {ListNode* dummy new ListNode(-1);dummy-next head;ListNode* prevNode dummy;for (int i 0; i left-1; i) {prevNode prevNode-next;}ListNode* nextNode;ListNode* currNode prevNode-next;for (int i 0; i right - left; i) {nextNode currNode-next;currNode-next nextNode-next;nextNode-next prevNode-next;prevNode-next nextNode;}return dummy-next;}
};复杂度分析
时间复杂度 O ( N ) O(N) O(N)其中 N N N 是链表总节点数。最多只遍历了链表一次就完成了反转。
空间复杂度 O ( 1 ) O(1) O(1)。只使用到常数个变量。
其他语言
python3
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写在最后
如果文章内容有任何错误或者您对文章有任何疑问欢迎私信博主或者在评论区指出 。
如果大家有更优的时间、空间复杂度方法欢迎评论区交流。
最后感谢您的阅读如果感到有所收获的话可以给博主点一个 哦。
