題目描述
反轉(zhuǎn)從位置 m 到 n 的鏈表极颓。請使用一趟掃描完成反轉(zhuǎn)朱盐。
說明:
1 ≤ m ≤ n ≤ 鏈表長度。
示例:
輸入: 1->2->3->4->5->NULL, m = 2, n = 4
輸出: 1->4->3->2->5->NULL
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/reverse-linked-list-ii
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有菠隆。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)兵琳，非商業(yè)轉(zhuǎn)載請注明出處。
解題思路
其實這是鏈表翻轉(zhuǎn)的變種骇径，以前我使用的鏈表翻轉(zhuǎn)一直是插入法躯肌，即把后面的節(jié)點插入到前面中間去，這樣需要保存插入位置既峡。
代碼如下：
# 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 m == n : return head
# 添加一個前驅(qū)節(jié)點
result = ListNode(0)
result.next = head
num = 0
cur = result
while num < m-1 :
cur = cur.next
num += 1
# 當(dāng)前節(jié)點的下一個節(jié)點為m羡榴，翻轉(zhuǎn)節(jié)點從這里開始插入
if num == m - 1 :
mprenode = cur
revnodehead = cur.next # 翻轉(zhuǎn)節(jié)點頭
revnodeend = cur.next # 設(shè)置翻轉(zhuǎn)尾節(jié)點
cur = cur.next # cur設(shè)置為翻轉(zhuǎn)范圍內(nèi)的第一個節(jié)點
num += 1
while (m <= num+1 <= n) :
# 從第二個節(jié)點開始翻轉(zhuǎn)
if m+1 <= num+1 <= n:
# 翻轉(zhuǎn)節(jié)點
temp = cur.next
cur.next = temp.next # 因為n小于鏈表長度校仑，所以temp肯定存在
temp.next = revnodehead # 斷開temp的后續(xù)節(jié)點 插入到翻轉(zhuǎn)頭之前
revnodehead = temp # 更新翻轉(zhuǎn)節(jié)點頭
num += 1
mprenode.next = revnodehead # 連接翻轉(zhuǎn)節(jié)點頭
revnodeend.next = cur.next # 節(jié)點尾
return result.next
鏈表翻轉(zhuǎn)還可以有另外一種方法卦方，我稱之為掉落法尘吗，把第一個要翻轉(zhuǎn)的節(jié)點從前面切斷近刘，它的后面節(jié)點依次切斷介劫，翻轉(zhuǎn)連接的方向踢京，然后依次向后遍歷翔烁，最后把最后一個節(jié)點和原序列連接。
class Solution:
# @param head, a ListNode
# @param m, an integer
# @param n, an integer
# @return a ListNode
def reverseBetween(self, head, m, n):
if m == n:
return head
dummyNode = ListNode(0)
dummyNode.next = head
pre = dummyNode
for i in range(m - 1):
pre = pre.next
# reverse the [m, n] nodes
reverse = None
cur = pre.next
for i in range(n - m + 1):
next = cur.next
cur.next = reverse
reverse = cur
cur = next
pre.next.next = cur
pre.next = reverse
return dummyNode.next
