題目要求：

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For examples:

Given 1->2->3->4->5->NULL, m = 2 and n = 4,
return 1->4->3->2->5->NULL.

解題思路：尋找關(guān)鍵節(jié)點(diǎn)

• 將head后移m-1個(gè)位置，找到逆置節(jié)點(diǎn)，記錄其前驅(qū)節(jié)點(diǎn)和自己卷雕。

  
  
  步驟一

• 從head節(jié)點(diǎn)開(kāi)始逆置，逆置（m-n+1）個(gè)節(jié)點(diǎn)

• 將所有節(jié)點(diǎn)相連

  
  
  步驟二棠耕、三

class ListNode():
    def __init__(self, x):
        self.val = x
        self.next = None

    def __repr__(self):
        if self:
            return "{} -> {}".format(self.val, repr(self.next))

class Solution(object):
    def reverseBetween(self, head, m, n):
        """
        :type head: ListNode
        :type m: int
        :type n: int
        :rtype: ListNode
        """
        # 有可能是從第一個(gè)節(jié)點(diǎn)開(kāi)始逆序，所以pre指針并不能指向head柠新，pre指針一般都是置為None

        pre = None
        m = m - 1
        length = n - m
        result = head

        # 將head放在逆序的開(kāi)始位置
        while head and m:
            pre = head
            head = head.next
            m -= 1

        # 逆序的第一個(gè)節(jié)點(diǎn)將是逆序后的最后一個(gè)節(jié)點(diǎn)窍荧，需要保存為tail
        new_node = None
        next = None
        tail = head
        while head and length:
            next = head.next
            head.next = new_node
            new_node = head
            head = next
            length -= 1
        tail.next = head

        if pre:
            pre.next = new_node
        else:
            result = new_node

        return result

if __name__ == "__main__":
    head = ListNode(1)
    head.next = ListNode(2)
    head.next.next = ListNode(3)
    head.next.next.next = ListNode(4)
    head.next.next.next.next = ListNode(5)
    print(Solution().reverseBetween(head, 2, 4))

自己的新方法：

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def reverseBetween(self, head, m, n):
        """
        :type head: ListNode
        :type m: int
        :type n: int
        :rtype: ListNode
        """
        diff, dummy, cur = n - m + 1, ListNode(-1), head
        dummy.next = head
        
        last_unswapped = dummy
        while head and m > 1:   #將cur放在逆序的開(kāi)始位置,last_unsnapped
            cur, last_unswapped, m = cur.next, cur, m - 1
            
        prev = last_unswapped
        first_swapped = cur
        while cur and diff > 0:
            prev.next, cur.next, cur, diff = cur, prev.next, cur.next, diff - 1   #新學(xué)的方法，哈哈哈哈哈哈哈
        
        last_unswapped, first_swapped.next = prev, cur    #last_unswapped不要賦值
        
        return dummy.next