Leetcode 25. Reverse Nodes in k-Group 以每组k个结点进行链表反转(链表)

Leetcode 25. Reverse Nodes in k-Group 以每组k个结点进行链表反转(链表)

题目描述

已知一个链表,每次对k个节点进行反转,最后返回反转后的链表

测试样例

Input: k = 2, 1->2->3->4->5
Output: 2->1->4->3->5


Input: k = 3, 1->2->3->4->5
Output: 3->2->1->4->5

详细分析

按照题目要求做就行了:比如k=2,首先[1->2->3->4->5]分组为[1->2],[3->4],[5],然后每组反转[2->1],[4->3],[5],最后输出反转后的链表[2->1->4->3->5]。

算法实现

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

        ListNode * cur = head;
        while(true){
            partialReverse(cur,k);
        
            for(int i=0;i<k;i++){
                cur=cur->next;
                if(cur==nullptr){
                    return head;
                }
            }
        }
    }
     
    // it's a closed interval
    void partialReverse(ListNode * start,int k){
        // 1->2
        // 1->2->3->4->5
        std::stack<int> vec;
        ListNode  * temp = start;
        for(int i=0;i<k;i++){
            vec.push(temp->val);
            temp = temp->next;
            if(i!=k-1 && temp==nullptr){
                return;
            }
        }
    
        for(int i=0;i<k;i++){
            int val = vec.top();
            vec.pop();
            start->val = val;
            start=start->next;
        }
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏尾尾部落

[剑指offer] 反转链表

设置三个指针,head为当前节点,pre为当前节点的前一个节点,next为当前节点的下一个节点,需要pre和next的目的是让当前节点从pre->head->n...

1562
来自专栏swag code

swap()交换两个变量的方法汇总

1054
来自专栏五分钟学算法

每天一算:Reverse String

我们会在每天早上8点30分准时推送一条LeetCode上的算法题目,并给出改题目的动画解析以及参考答案,每篇文章阅读时长为五分钟左右。

912
来自专栏程序生活

求一个数n次方后的末尾数(数论/快速幂)问题描述解题思路代码实现运行结果参考

问题描述 hdu1061-Rightmost Digit hdu1097-A hard puzzle 这两个oj题目思路几乎一样,都是为了快速求出一个数n次...

4737
来自专栏java达人

Java 中正确使用 hashCode 和 equals 方法

在这篇文章中,我将告诉大家我对hashCode和equals方法的理解。我将讨论他们的默认实现,以及如何正确的重写他们。我也将使用Apache Commons提...

3726
来自专栏Golang语言社区

Golang 中"泛型"的支持

Golang不支持一般的类似java中的标记式泛型。很多人因此而十分不满,认为没有泛型增加了很多工作量。而目前由于泛型支持的复杂性,Golang的设计和实现者并...

38513
来自专栏chenjx85的技术专栏

leetcode-204-Count Primes

2588
来自专栏木子昭的博客

寻找"单身数"

一个有N个数的数组里, 每个数字都出现两次, 现在取出一个数, 根据剩下的数字, 猜测取出的数的值(要求时间复杂度为N, 空间复杂度为1) 异或运算 两个相同...

2685
来自专栏和蔼的张星的图像处理专栏

165. 合并两个排序链表双指针

将两个排序链表合并为一个新的排序链表. 样例 给出 1->3->8->11->15->null,2->null, 返回 1->2->3->8->11->15...

953
来自专栏ml

java学习之协调同步的线程

            当一个线程使用的同步方法中用到某个变量,而此变量有需要其他线程修改后才能符合本线程的需要,      那么可以在同步方法中使用wait(...

3379

扫码关注云+社区

领取腾讯云代金券