LeetCode 25 Reverse Nodes in k-Group

标签: 链表问题 LeetCode 发布于:2022-02-05 21:05:50 编辑于:2022-02-05 22:57:32 浏览量:393

题目分析

https://leetcode.com/problems/reverse-nodes-in-k-group/

迭代法

class Solution {
public:
    ListNode *reverseKGroup(ListNode *head, int k) {
        if (head == nullptr) return head;
        if (k == 1) return head;

        int n = 0;
        ListNode *next = head;
        while (next != nullptr) {
            n++;
            next = next->next;
        }
        int stop = k * int(n / k);
        int count = -1;

        ListNode dummyNode;
        ListNode *prevGroupHead = &dummyNode;
        ListNode *groupHead = head;
        ListNode *c = head;
        ListNode *cn = c->next;
        while (true) {
            count++;
            // c is the count-th node, start from 0
            if (count == stop) break;
            if ((count + 1) % k == 0) {
                // cn is in next group
                prevGroupHead->next = c;
                // The old head becomes the tail
                prevGroupHead = groupHead;
                groupHead = cn;
                // Update c & cn
                if (cn) {
                    c = cn;
                    cn = cn->next;
                } else {
                    break;
                }

            } else {
                auto cnn = cn->next;
                cn->next = c;
                c = cn;
                cn = cnn;
            }
        }
        prevGroupHead->next = groupHead;
        return dummyNode.next;
    }
};

递归法

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* c = head;
        int count = 1;
        while (c) {  // 循环结束要么 c 为 nullptr
            if (count == k) {
                break;  // 要么够了,此时 c 必不为 nullptr
            }
            count++;
            c = c->next;
        }
        if (!c) return head;  // 所以只需要判断 c 是否是 nullptr 就好
        
        auto rest = reverseKGroup(c->next, k);
        c->next = nullptr;
        auto temp = reverse(head);
        head->next = rest;
        return temp;
        
    }
    
    ListNode* reverse(ListNode* head) {
        if (!head || !head->next) return head;
        auto temp = reverse(head->next);
        head->next->next = head;
        head->next = nullptr;
        return temp;
    }
};

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