92. Reverse Linked List II

https://leetcode.com/problems/reverse-linked-list-ii/

solution

• 迭代

class Solution:
    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        dummy = ListNode(val=-1, next=head)

        pre = dummy
        for _ in range(left - 1):
            pre = pre.next
        
        cur = pre.next
        for _ in range(right - left):  # prev-cur-temp: 1234 -> 1324 -> 1432
            temp = cur.next

            cur.next = temp.next
            temp.next = pre.next # 注意这里是pre.next 而不是 cur            
            pre.next = temp
        return dummy.next

时间复杂度：O(n) 空间复杂度：O(1)

• 递归