題目

解題概念

  • 此題簡單來說，就是題目會指定 left 和 right，我們需要將介於第 left 個和第 right 個節點的所有節點反轉
  • 而在實際執行上，我採用迴圈的方式 :
    1. 因為 left 必 <= right，故先用 reverseBetween() 函數遞迴，將 left 移為欲反轉的第一個節點處
    2. 接著用 reverseN() 函數遞迴反轉

實際寫Code

  • 目標函式 : reverseBetween(head, left, right)
    • Input : head: ListNode、left: int、right: int
    • Output : ListNode
  • 主要程式碼 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    succ = ListNode()
    def reverseN(self, head, r):
        if r == 1 :
            self.succ = head.next
            return head
        last = self.reverseN(head.next, r-1)
        head.next.next = head
        head.next = self.succ
        return last 

    def reverseBetween(self, head, left, right):
        if left == 1:
            return self.reverseN(head, right)
        head.next = self.reverseBetween(head.next, left-1, right-1)
        return head