LeetCode 25-Reverse Nodes in k-Group(链表反转)

LeetCode 25 Reverse Nodes in k-Group

题干:

k个k个一组反转链表,若最后一组不足k个,则不反转。

Input: head = [1,2,3,4,5], k = 2
Output: [2,1,4,3,5]

解:

借助反转链表模板题的迭代法,“反转以a为头节点的链表”实际就是“反转a到null之间的节点”,扩展到“反转a到b之间的节点”,只需把代码里的null改成b即可(注意区间是左闭右开[a,b))。

而对整个链表k个一组进行反转,只需递归地每次去反转当前链表的前k个(不足的不反转),并将反转后的链表与后续进行连接。

ListNode* reverse(ListNode* a, ListNode* b){ //反转区间[a, b)的元素,注意是左闭右开
        ListNode* prev = b, *cur = a;
        while(cur != b){
            ListNode* tmp = cur->next;
            cur->next = prev;
            prev = cur;
            cur = tmp;
        }
        return prev;
    }

ListNode* reverseKGroup(ListNode* head, int k) {
        if(!head) return nullptr;
        ListNode* a = head, *b = head;
        for(int i = 0; i < k; i++){
            if(!b) return head; // 不足k个,不需要反转
            b = b->next;
        }
        ListNode* newHead = reverse(a, b); //b为第(k+1)个节点
        a->next = reverseKGroup(b, k);
        return newHead;
    }

版权声明:本文为PriscillaZhao原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
THE END
< <上一篇
下一篇>>