又是一道升級(jí)題窒典，還記得原來(lái)的翻轉(zhuǎn)鏈表嘛蟆炊，這個(gè)是要求指定m和n翻轉(zhuǎn)鏈表∑僦荆或許你忘了鏈表翻轉(zhuǎn)怎么做涩搓，我編一個(gè)口訣：
要問(wèn)把一個(gè)鏈表翻轉(zhuǎn)分幾步，總共分五步劈猪，第一步定義一個(gè)新鏈表和pre為空的鏈表昧甘，第二步拿掉cur的頭節(jié)點(diǎn)，第三步岸霹，pre節(jié)點(diǎn)給cur.next疾层，第四步，cur的頭結(jié)點(diǎn)給pre贡避，第五步痛黎，更新cur(用tmp)予弧。除了那個(gè)對(duì)列實(shí)現(xiàn)，都可以用這個(gè)口訣湖饱，當(dāng)然對(duì)列實(shí)現(xiàn)是最好理解的掖蛤。
1.題目
原題
反轉(zhuǎn)從位置 m 到 n 的鏈表。請(qǐng)使用一趟掃描完成反轉(zhuǎn)井厌。
說(shuō)明:
1 ≤ m ≤ n ≤ 鏈表長(zhǎng)度蚓庭。
例子
輸入: 1->2->3->4->5->NULL, m = 2, n = 4
輸出: 1->4->3->2->5->NULL
2.解析
這道題關(guān)鍵是鏈表的拆分和合并，小知識(shí)點(diǎn)仅仆。
- 新生成鏈表的常用方法器赞，定義一個(gè)頭部節(jié)點(diǎn)，然后指向head墓拜，為了保留原鏈表的特點(diǎn)港柜，將他賦值給另一個(gè)鏈表，遍歷另一個(gè)鏈表咳榜，可以改變這個(gè)鏈表的指向夏醉。
- 指定start和next，start直到開(kāi)始反轉(zhuǎn)的前一個(gè)節(jié)點(diǎn)涌韩，end為結(jié)束反轉(zhuǎn)前的最后一個(gè)節(jié)點(diǎn)畔柔。
- start用start.next更新，end和cur更新為start臣樱，pre初始化為None靶擦，然后鏈表反轉(zhuǎn)。
- 更新start.next為pre擎淤，end.next為cur
3.python代碼
class Solution:
def reverseBetween(self, head, m, n):
if head is None or head.next is None:
return head
new = ListNode(0)
new.next = head
start = new
for i in range(m-1):
start = start.next#m-2個(gè)節(jié)點(diǎn)
end = cur = start.next
pre = None
for i in range(n-m+1):
next = cur.next
cur.next = pre#翻轉(zhuǎn)過(guò)程奢啥，記住
pre = cur
cur = next
start.next = pre
end.next = cur
return new.next
