LeetCode

LeetCode-25 K个一组翻转链表

nkul · 9月7日 · 2020年 45次已读
  • 首节点也要翻转,故添加虚拟头结点
  • 判断后续是否还有k个节点
  • k个节点内部反序
  • 调整k个节点首尾指针
  • 进行下k个翻转
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        auto dummy  = new ListNode(-1);
        dummy->next = head;
        for(auto cur = dummy;;){
            //判断后面是否还有k个元素
            auto p = cur;
            for(int i=0;i < k && p; i++) p = p->next;
            if(!p) break;

            //交换k个元素内部的顺序
            auto a = cur->next, b= a->next;
            //k个元素内部翻转进行k-1次
            for(auto i = 0;i < k - 1 ;i++){
                //记录下一节点
                auto c = b->next;
                b->next = a;
                a = b, b = c;
            }

            //修改头尾指针
            auto c = cur->next;
            cur->next = a;
            c->next = b;
            //下k个继续
            cur = c;
        }
        return dummy->next;
    }
};


0 条回应

必须 注册 为本站用户, 登录 后才可以发表评论!