92. 反转链表 II

题目

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

示例 1：

输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]

示例 2：

输入：head = [5], left = 1, right = 1
输出：[5]

提示：

• 链表中节点数目为 n
• 1 <= n <= 500
• -500 <= Node.val <= 500
• 1 <= left <= right <= n

解答

思路

思路和 反转链表 是一致的，我们记住一些性质，当反转结束后：

• pre 指向原先链表的末尾
• cur 指向原先链表末尾的下一个位置

因此反转这一段之后：

• p0->val = 1 应该指向链表的末尾，也就是 p0->next = pre
• left->val = 2 原先表头应该指向链表末尾的下一个位置，也就是 left->next = cur
• 注意当 left == 1 时，也就是头节点，我们没有 p0，因此我们加上一个 哨兵节点

复杂度：

• 时间复杂度为 $O(n)$
• 空间复杂度为 $O(1)$

代码

C++ 代码

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        auto dummy = new ListNode(-1);
        dummy->next = head;
        auto p0 = dummy;

        for (int i = 1; i < left; i ++) {
            p0 = p0->next;
        }

        ListNode* pre = nullptr;
        ListNode* cur = p0->next;

        for (int i = 0; i < right - left + 1; i ++) {
            ListNode* nxt = cur->next;

            cur->next = pre;
            pre = cur;
            cur = nxt;
        }

        p0->next->next = cur;
        p0->next = pre;

        return dummy->next;                                   
    }
};

Python 代码

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

        for _ in range(left - 1):
            p0 = p0.next
        
        pre = None
        cur = p0.next

        for _ in range(right - left + 1):
            nxt = cur.next
            cur.next = pre
            pre = cur
            cur = nxt
        
        p0.next.next = cur
        p0.next = pre

        return dummy.next # head 可能已经修改了