侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【迭代, 递归】反转链表 II

GabrielxD
2022-09-22 / 0 评论 / 0 点赞 / 27 阅读 / 1,129 字 / 正在检测是否收录...

题目

92. 反转链表 II


给你单链表的头指针 head 和两个整数 leftright ,其中 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

进阶: 你可以使用一趟扫描完成反转吗?

解题

方法一:递归

思路

首先在 【迭代, 递归】反转链表 - 方法一:递归 的基础上实现反转链表前 N 个节点
比如说对于下图链表,执行 reverseN(head, 3)

img

解决思路和反转整个链表差不多,只要稍加修改即可:

ListNode succ = null; // 后驱节点

// 反转以 head 为起点的 n 个节点,返回新的头结点
ListNode reverseN(ListNode head, int n) {
    if (n == 1) {
        // 记录第 n + 1 个节点
        succ = head.next;
        return head;
    }
    // 以 head.next 为起点,需要反转前 n - 1 个节点
    ListNode newHead = reverseN(head.next, n - 1);
    head.next.next = head;
    // 让反转之后的 head 节点和后面的节点连起来
    head.next = succ;
    return newHead;
}

具体的区别:

  1. base case 变为 n == 1,反转一个元素,就是它本身,同时要记录后驱节点
  2. 之前反转整个链表时直接把 head.next 设置为 null,因为整个链表反转后原来的 head 变成了整个链表的最后一个节点。但现在 head 节点在递归反转之后不一定是最后一个节点了,所以要记录后驱(succ)(第 n + 1 个节点),反转之后将 head 连接上。
    img

接下来解决本题,当 left == 1 时,就相当于反转链表开头的 right 个元素,也就是刚才实现的功能:

ListNode reverseBetween(ListNode head, int left, int right) {
    // base case
    if (left == 1) {
        // 相当于反转前 right 个元素
        return reverseN(head, right);
    }
    // ...
}

left > 1 时也可以递归到 left == 1 的情况:

class Solution {
    // ...
    public ListNode reverseBetween(ListNode head, int left, int right) {
        // base case
        if (left == 1) return reverseN(head, right);
        // 前进到反转的起点触发 base case
        head.next = reverseBetween(head.next, left - 1, right - 1);
        return head;
    }
    // ...
}

注意:递归的返回的头节点要接回到前面未反转链表的后面,防止链表断掉。

参考:递归魔法:反转单链表

代码

class Solution {
    ListNode succ = null;

    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (left == 1) return reverseN(head, right);
        head.next = reverseBetween(head.next, left - 1, right - 1);
        return head;
    }

    ListNode reverseN(ListNode head, int n) {
        if (n == 1) {
            succ = head.next;
            return head;
        }
        ListNode newHead = reverseN(head.next, n - 1);
        head.next.next = head;
        head.next = succ;
        return newHead;
    }
}

不把 succ 维护成全局变量的实现:

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (left == 1) return reverseN(head, right)[0];
        head.next = reverseBetween(head.next, left - 1, right - 1);
        return head;
    }

    ListNode[] reverseN(ListNode head, int n) {
        if (n == 1) return new ListNode[]{head, head.next};
        ListNode[] arr = reverseN(head.next, n - 1);
        head.next.next = head;
        head.next = arr[1];
        return arr;
    }
}
class Solution {
    pair<ListNode*, ListNode*> reverseN(ListNode* head, int n) {
        if (n == 1) return {head, head->next};
        auto pr = reverseN(head->next, n - 1);
        head->next->next = head;
        head->next = pr.second;
        return pr;
    }

public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        if (left == 1) return reverseN(head, right).first;
        head->next = reverseBetween(head->next, left - 1, right - 1);
        return head;
    }
};

方法二:迭代

思路

反转链表的部分与 【迭代, 递归】反转链表 - 方法二:迭代 完全相同。
先维护一个哨兵节点(dummy)在头节点前面防止头节点被反转时出问题,迭代到链表的第 left-1 个节点,记录下该节点(beforePart),以便于之后把反转后的链表接回去,然后再往后推一个节点就是需要反转部分的头节点,同时也是反转完成后的尾节点(partTail),记录下该节点以便于之后把反转后链表的尾节点接上原链表后面。然后就可以把从当前节点开始的 right-left+1 个节点反转了再拼接回去即可。

动画

代码

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummy = new ListNode(-1, head), curr = dummy;
        int n = right - left + 1;
        while (left-- > 1) curr = curr.next;
        ListNode beforePart = curr, newNext = null, newPrev = null;
        curr = curr.next;
        ListNode partTail = curr;
        for (int i = 0; i < n; ++i) {
            newPrev = curr.next;
            curr.next = newNext;
            newNext = curr;
            curr = newPrev;
        }
        partTail.next = newPrev;
        beforePart.next = newNext;
        return dummy.next;
    }
}
0

评论区