?LeetCode刷題實戰(zhàn)92：反轉(zhuǎn)鏈表 II
算法的重要性，我就不多說了吧，想去大廠，就必須要經(jīng)過基礎(chǔ)知識和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個公眾號后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選 ！
今天和大家聊的問題叫做?反轉(zhuǎn)鏈表 II，我們先來看題面：
https://leetcode-cn.com/problems/reverse-linked-list-ii/
Reverse a linked list from position m to n. Do it in one-pass.
Note: 1 ≤ m ≤ n ≤ length of list.
題意
輸入: 1->2->3->4->5->NULL, m = 2, n = 4
輸出: 1->4->3->2->5->NULL
解題
題解
class?Solution:
????def?reverseBetween(self, head:?ListNode, m:?int, n:?int)?-> ListNode:
????????if?m == n:
????????????return?head
????????
????????pnt = head
????????# 移動m-2格，到達翻轉(zhuǎn)部分的前驅(qū)節(jié)點
????????for?i in?range(m-2):
????????????pnt = pnt.next
????????????
????????
????????flag = False
????????# 特判m=1的情況，如果m=1那么人為制造一個節(jié)點作為前驅(qū)
????????if?m == 1:
????????????flag = True
????????????pnt = ListNode(0)
????????????pnt.next?= head
????????????head = pnt
????????????
????????# cur即當(dāng)前待翻轉(zhuǎn)的節(jié)點
????????cur = pnt.next
????????# pre表示cur的前驅(qū)
????????pre = pnt
????????# last表示最后一個翻轉(zhuǎn)的元素
????????last = pnt.next
????????????
????????for?i in?range(m, n+1):
????????????# 先記錄下當(dāng)前節(jié)點的后繼
????????????nxt = cur.next
????????????# 將當(dāng)前節(jié)點的后繼指向前驅(qū)
????????????cur.next?= pre
????????????pnt.next?= cur
????????????pre = cur
????????????cur = nxt
????????????
????????# 將last指向翻轉(zhuǎn)之后的元素，將鏈表串起來
????????last.next?= cur
????????return?head.next?if?flag else?head
總結(jié)
上期推文：