LeetCode 92.反转链表II
内容纲要

原题链接:https://leetcode.cn/problems/reverse-linked-list-ii/description/

image-20240203214807793

迭代法:(自己写的不美观版)

class Solution
{
public:
    ListNode *reverseBetween(ListNode *head, int left, int right)
    {
        if (head == NULL || head->next == NULL || left == right)
            return head;
        //slow,fast,p 三个指针是转置操作需要
        //H,E,HEAD,END四个分别记录区间前后位置,及区间头尾位置
        ListNode *slow = NULL, *fast = head, *p, *H = NULL, *E, *HEAD, *END;
        ListNode *first = head;//记录头结点位置,如果不是从头结点开转的就用得上
        for (int i = 1; i <= right +1; i++)
        {
            if (i == left - 1)
                H = fast;//记录区间前一个位置
            else if (i >= left && i <= right)//开始转置
            {
                if (i == left)
                    END = fast;//记录反转后的区间尾
                else if (i == right)
                    HEAD = fast;//记录反转后的区间头
                //转置操作同反转链表I
                p = fast;
                fast = fast->next;
                p->next = slow;
                slow = p;
            }
            else if (i == right + 1)
            {
                E = fast;//记录区间后一个位置
                if(H != NULL)
                    H->next = HEAD;//将反转后的区间头连接
                if(E != NULL)
                    END->next = E;//将反转后的区间尾连接
                break;
            }
            if (i < left)
                fast = fast->next;//在反转操作开始之前一直迭代
        }
        if (left == 1)
            return HEAD;
        else
            return first;
    }
};

迭代法(官方答案):

class Solution {
private:
    void reverseLinkedList(ListNode *head) {
        ListNode *pre = nullptr;
        ListNode *cur = head;

        while (cur != nullptr) {
            ListNode *next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
    }

public:
    ListNode *reverseBetween(ListNode *head, int left, int right) {
        // 因为头节点有可能发生变化,使用虚拟头节点可以避免复杂的分类讨论
        ListNode *dummyNode = new ListNode(-1);
        dummyNode->next = head;

        ListNode *pre = dummyNode;
        // 第 1 步:从虚拟头节点走 left - 1 步,来到 left 节点的前一个节点
        // 建议写在 for 循环里,语义清晰
        for (int i = 0; i < left - 1; i++) {
            pre = pre->next;
        }

        // 第 2 步:从 pre 再走 right - left + 1 步,来到 right 节点
        ListNode *rightNode = pre;
        for (int i = 0; i < right - left + 1; i++) {
            rightNode = rightNode->next;
        }

        // 第 3 步:切断出一个子链表(截取链表)
        ListNode *leftNode = pre->next;
        ListNode *curr = rightNode->next;

        // 注意:切断链接
        pre->next = nullptr;
        rightNode->next = nullptr;

        // 第 4 步:同第 206 题,反转链表的子区间
        reverseLinkedList(leftNode);

        // 第 5 步:接回到原来的链表中
        pre->next = rightNode;
        leftNode->next = curr;
        return dummyNode->next;
    }
};

递归法:

借鉴于大佬labuladong

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

private:
    ListNode* successor = nullptr; // 后驱节点
    // 反转以 head 为起点的 n 个节点,返回新的头结点
    ListNode* reverseN(ListNode* head, int n) 
    {
        if (n == 1) 
        {
            // 记录第 n + 1 个节点
            successor = head->next;
            return head;
        }
        // 以 head->next 为起点,需要反转前 n - 1 个节点
        ListNode* last = reverseN(head->next, n - 1);

        head->next->next = head;
        // 让反转之后的 head 节点和后面的节点连起来
        head->next = successor;
        return last;
    }
};

对于函数reverseN

1、base case 变为 n == 1,反转一个元素,就是它本身,同时要记录后驱节点

2、刚才我们直接把 head.next 设置为 null,因为整个链表反转后原来的 head 变成了整个链表的最后一个节点。但现在 head 节点在递归反转之后不一定是最后一个节点了,所以要记录后驱 successor(第 n + 1 个节点),反转之后将 head 连接上。

image-20240204013239546

对于函数reverseBetween

image-20240204013402415

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇