題目鏈接
難度：中等 ??????類型： 鏈表
反轉(zhuǎn)從位置 m 到 n 的鏈表桐玻。請(qǐng)使用一趟掃描完成反轉(zhuǎn)串远。
說明:
1 ≤ m ≤ n ≤ 鏈表長(zhǎng)度。
示例
輸入: 1->2->3->4->5->NULL, m = 2, n = 4
輸出: 1->4->3->2->5->NULL
解題思路
0.保存頭節(jié)點(diǎn)
1.找到反轉(zhuǎn)部分的前一個(gè)節(jié)點(diǎn)，保存為start
2.翻轉(zhuǎn)第m到n位鏈表扼褪，記錄第m個(gè)節(jié)點(diǎn)為node_m舱污，第n個(gè)節(jié)點(diǎn)為node_n呀舔，第n+1個(gè)節(jié)點(diǎn)為end
3.連接鏈表，start.next = node_n, node_m.next = end
4.返回頭節(jié)點(diǎn)
代碼實(shí)現(xiàn)
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
if not head or not head.next or m==n:
return head
dummy = ListNode(0)
dummy.next = head
start = dummy
for i in range(m-1):
start = start.next
end = cur = start.next
pre = None
for i in range(n-m+1):
next = cur.next
cur.next = pre
pre = cur
cur = next
start.next = pre
end.next = cur
return dummy.next
