###### tags: `Leetcode` `medium` `list` `python`

# 92. Reverse Linked List II

## [題目連結:] https://leetcode.com/problems/reverse-linked-list-ii/

## 題目:
Given the ```head``` of a singly linked list and two integers ```left``` and ```right``` where ```left <= right```, reverse the nodes of the list from position ```left``` to position ```right```, and return the reversed list.


#### [圖片來源:] https://leetcode.com/problems/reverse-linked-list-ii/

## 解題想法:
* 題目為給一list，並給兩個位置left,right
* head為位置1
* 對於left,right之中間所有node進行reverse
* 流程:
* 設dummy node
* dummy=ListNode(0)
* dummy.next=head
* start=dummy
* 開頭left-1個node不用移動

    for i in range(left-1):
        start=start.next 

* reverse: 可參考[206. Reverse Linked List](/z1pdr-lnSSeFKiibqOM3aA)
* init:
* tail=start.next 即為要處理的node
* tmp=tail 代替tail移動
* pre=None
* cur=tail
* 反轉right-left+1個node
* 最終記得要將頭尾連到正確的位置
* 示意圖: (潦草請見諒)

## Python:

class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
    def insert(self,node):
        if self.next==None:
            self.next=ListNode(node)
        else:
            self.next.insert(node)
    def printList(self):
        head=self
        tmp = []
        while head:
            tmp.append(head.val)
            head=head.next
        print(tmp)

class Solution(object):
    def reverseBetween(self, head, left, right):
        """
        :type head: ListNode
        :type left: int
        :type right: int
        :rtype: ListNode
        """
        dummy=ListNode(0)
        dummy.next=head
        start=dummy
        #開頭left-1個node不用移動
        for i in range(left-1):
            start=start.next
        #init:
        tail=start.next #開始反轉的head
        tmp=tail
        pre=None
        cur=tail
        #reverse: right-left+1個node
        for i in range(right-left+1):
            cur=cur.next #先記錄下個位置
            tmp.next=pre #指回去
            #往後移動處理下一組
            pre=tmp
            tmp=cur
        #尾巴要指到正確位置
        start.next=pre
        tail.next=cur
        return dummy.next 
        
head = ListNode(1)
head.insert(2)
head.insert(3)
head.insert(4)
head.insert(5)
head.printList()

result = Solution()
ans = result.reverseBetween(head,2,4)
ans.printList()