題目描述

反轉(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