25.K 个一组翻转链表 (Hard)*

题目描述*

给你一个链表，每 k 个结点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果结点总数不是 k 的整数倍，那么请将最后剩余的结点保持原有顺序。

示例*

给定这个链表：1->2->3->4->5

当 k = 2 时，应当返回: 2->1->4->3->5

当 k = 3 时，应当返回: 3->2->1->4->5

说明*

你的算法只能使用常数的额外空间。
你不能只是单纯的改变结点内部的值，而是需要实际的进行结点交换。

代码*

链表反转很简单，主要就是要每 k 个截断，然后不足的不反转。迭代最好把图画出来，不然脑子想不太出来。

递归迭代

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        if(head == nullptr) {
            return nullptr;
        }
        ListNode *p = head;
        int i = k;
        while(i > 1) {
            p = p->next;
            if(p == nullptr) {
                return head;
            }
            i--;
        }
        ListNode *nextHead = p->next;
        p->next = nullptr;
        ListNode *newHead = reverse(head);
        head->next = reverseKGroup(nextHead, k);
        return newHead;
    }
    ListNode* reverse(ListNode *head) {
        ListNode *slow = nullptr, *fast = head;
        while(fast != nullptr) {
            ListNode *p = fast->next;
            fast->next = slow;
            slow = fast;
            fast = p;
        }
        return slow;
    }
};

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode *dummy = new ListNode(-1);
        dummy->next = head;
        ListNode *slow = dummy, *fast = dummy;
        while(fast->next != nullptr) {
            for(int i = 0; i < k && fast != nullptr; i++) {
                fast = fast->next;
            }
            if(fast == nullptr) {
                break;
            }
            ListNode *curHead = slow->next;
            ListNode *nextHead = fast->next;
            fast->next = nullptr;
            slow->next = reverse(curHead);
            curHead->next = nextHead;
            slow = curHead;
            fast = slow;
        }
        return dummy->next;
    }
    ListNode* reverse(ListNode* head) {
        ListNode *slow = nullptr, *fast = head;
        while(fast != nullptr) {
            ListNode *p = fast->next;
            fast->next = slow;
            slow = fast;
            fast = p;
        }
        return slow;
    }
};

最后更新: July 23, 2022