LeetCode 92 Reverse Linked List II

Tag: 链表问题 LeetCode Posted on 2022-02-05 20:44:38 Edited on 2022-02-05 21:04:05 Views: 176

题目分析

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

直接法

显然,我们可以手动剔除链表前面和后面无需翻转的部分,中间部分翻转好之后再进行拼接。

实现上有点绕,还需多加练习!

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        ListNode dummy(0, head);
        auto cur = &dummy;
        auto l = head;
        auto r = head;
        for (int i = 0; i <= right; i++) {
            if (i == left - 1) l = cur;
            if (i == right) r = cur;
            cur = cur->next;
        }
        auto rest = r->next;
        r->next = nullptr;
        auto t = reverse(l->next);
        l->next->next = rest;
        l->next = t;
        return dummy.next;
    }
    
    ListNode* reverse(ListNode* head) {
        if (!head || !head->next) return head;
        auto newTail = head->next;
        auto newHead = reverse(head->next);
        newTail->next = head;
        head->next = nullptr;
        return newHead;
    }
};

更加优雅的递归实现

https://labuladong.gitee.io/algo/2/17/17/

将问题转换为翻转前 n 个元素。

class Solution {
public:
    ListNode* suffix = nullptr;
    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) {
            suffix = head->next;
            return head;
        }
        auto newHead = reverseN(head->next, n - 1);
        head->next->next = head;
        head->next = suffix;
        return newHead;
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/