## 題解

### 四指針反轉


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        if left == right: # 排除不需要反轉的鏈表
            return head

        dummy_head = ListNode() # 創建虛擬頭節點
        dummy_head.next = head
        plc_step = left - 1 # 計算 left cursor 前面的 pre left cursor 所需要走的步數
        nrc_step = right + 1 # 計算 right cursor 後面的 next right cursor 所需要走的步數
        plc = lc = rc = nrc = dummy_head # 創建四個指針

        # 根據所需要走到的步數，走到對應的位置
        while rc and nrc and lc and plc and right > 0 or nrc_step > 0 or plc_step > 0 or left > 0:
            if right > 0:
                rc = rc.next
                right -= 1
            if nrc_step > 0:
                nrc = nrc.next
                nrc_step -= 1
            if plc_step > 0:
                plc = plc.next
                plc_step -= 1
            if left > 0:
                lc = lc.next
                left -= 1
        
        # 切斷需要修改鍊錶的前面和後面
        plc.next = None
        rc.next = None
        
        # 開始反轉鍊錶
        pre = None
        cur = lc
        while cur:
            temp = cur.next
            cur.next = pre
            pre = cur
            cur = temp
        
        # 鏈表反轉完成以後需要接回去原本的鏈表中
        plc.next = rc # pre left cursor 接到 right cursor
        lc.next = nrc # left cursor 接到 next right cursor
        
        return dummy_head.next