LeetCode 92反转链表II Python3
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了LeetCode 92反转链表II Python3，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3173字，纯文字阅读大概需要5分钟。
内容图文
原题：链接
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明:
1 ≤ m ≤ n ≤ 链表长度。
示例：
解法一
其实刚开始看这道题也没啥特别的想法，直接迭代方法开干就行了。但是有很多细节需要处理，导致代码修改了很久才通过。这里简单地捋一下吧。设第m个节点为start节点，在后续节点的翻转操作之前，我们需要保存start节点的前一个节点front，因此为了使得程序便于处理一些边界条件，加入一个虚拟头结点vHead来作为front的初始值。而后利用到两个指针pre和cur交替移动变换来翻转链表，反转操作熟悉之后就可以轻松地解决，有兴趣可以看看自己对于反转链表的理解：
其中有迭代的方法和递归的方法。这里我们讨论迭代法，迭代需要一个临时变量t来存下一个cur节点，避免翻转后无法到达该节点。翻转完成之后，则直接处理头与尾的链接。此时pre节点指向的是第n个节点，我们把front节点指向它，而start节点就指向pre节点的下一个节点，也就是cur节点即可。
代码如下：
def reverseBetween(head):
if not head:
return head
i = 1
vHead = ListNode(-1)
vHead.next = head
temp = head
front = vHead
while i != m:
if i == m-1:
front = temp
i += 1
temp = temp.next
# 迭代反转
pre, cur = temp, temp.next
while cur and i != n:
t = cur.next
cur.next = pre
pre = cur
cur = t
i += 1
# front.next 即为 start 节点
front.next.next = cur
front.next = pre
return vHead.next
解法二
递归+回溯的思想参考的官方题解。这里仅仅做一个针对于自己理解的说明。
反转的操作也可以通过两两对换的形式来完成。正如LeeTCode 344 反转字符串一样。利用双指针法，其中i指向头，j指向尾，然后完成两两互换，并移动各自指针的位置，直到i == j，代码不难写出：
def reverseString(s):
n = len(s)
i, j = 0, n-1
while i < j:
s[i], s[j] = s[j], s[i]
i += 1
j -= 1
因此本题也可以借鉴这种思想，通过交换值来达到反转的目的。但面临的问题是，数组拥有索引方便取值，而单链表只有next指针。因此我们的想法是通过递归，使得需要指向交换头与尾的left和right指针齐头并进，先指到它们各自的位置，然后通过回溯完成交换与指针的移动。这里需要注意，回溯的目的，我们通过程序就可以看到，不仅完成了值的交换，也实现了right指针往前的效果，正如反转字符串中的j -= 1。不仅如此，我们还需要获得上一次递归结束left指针的位置作为我们程序终止的依据，这里我们仅在内部递归函数中改变不可变类型变量left的指向即可，因此在变量前添加关键字nonlocal(具体进一步了解可以搜索了解一下Python变量作用域的L(local)，E(enclosing)，G(global)，B(built-in)原则，变量名会按照局部->嵌套->全局->内置的优先级顺序进行搜索)。
最后的最后，再分析一下结束条件。考虑到链表个数为奇数或偶数，只要满足：
left == right or left == right.next
我们就可以停止交换，但是不能在此直接return，因为返回之后将会进行错误的继续交换操作。科学的做法就是设立一个标志位stop，当且仅当stop为False的时候才执行交换操作。参考代码如下：
def reverseBetween(head):
def recur_and_back(right, m, n):
nonlocal left
if n == 1:
# right 指向了正确的位置
return
right = right.next
if m > 1:
# 如果 left 没有指到其位置则继续
left = left.next
# 递归
recur_and_back(right, m-1, n-1)
if left == right or left == right.next:
# 后续停止交换了
self.stop = True
if not self.stop:
left.val, right.val = right.val, left.val
# 交换之后 left 需向后移一位
# right 则交由回溯实现向前
left = left.next
if not head:
return None
left, right = head, head
self.stop = False
recur_and_back(right, m, n)
return head
希望通过此题能加深对递归和回溯的理解。
Key Board 发布了9 篇原创文章 · 获赞 14 · 访问量 3284 私信 关注内容总结
以上是互联网集市为您收集整理的LeetCode 92反转链表II Python3全部内容，希望文章能够帮你解决LeetCode 92反转链表II Python3所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。