博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
[LintCode] Reverse Nodes in k-Group 每k个一组翻转链表
阅读量:5996 次
发布时间:2019-06-20

本文共 2945 字,大约阅读时间需要 9 分钟。

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

Example

Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

LeetCode上的原题,请参见我之前的博客。

解法一:

class Solution {public:    /**     * @param head a ListNode     * @param k an integer     * @return a ListNode     */    ListNode *reverseKGroup(ListNode *head, int k) {        ListNode *dummy = new ListNode(-1), *pre = dummy, *cur = pre;        dummy->next = head;        while (cur->next) {            int d = k;            while (cur->next && d-- > 0) {                cur = cur->next;            }            if (d > 0) return dummy->next;            ListNode *t = cur->next;            cur->next = NULL;            pre->next = reverse(pre->next);            for (int i = 0; i < k; ++i) pre = pre->next;            pre->next = t;            cur = pre;        }        return dummy->next;    }    ListNode* reverse(ListNode *head) {        ListNode *dummy = new ListNode(-1), *cur = head;        dummy->next = head;        while (cur && cur->next) {            ListNode *t = cur->next;            cur->next = t->next;            t->next = dummy->next;            dummy->next = t;        }        return dummy->next;    }};

解法二:

class Solution {public:    /**     * @param head a ListNode     * @param k an integer     * @return a ListNode     */    ListNode *reverseKGroup(ListNode *head, int k) {        ListNode *dummy = new ListNode(-1), *pre = dummy, *cur = pre;        dummy->next = head;        int num = 0;        while (cur = cur->next) ++num;        while (num >= k) {            cur = pre->next;            for (int i = 1; i < k; ++i) {                ListNode *t = cur->next;                cur->next = t->next;                t->next = pre->next;                pre->next = t;            }            pre = cur;            num -= k;        }        return dummy->next;    }};

解法三:

class Solution {public:    /**     * @param head a ListNode     * @param k an integer     * @return a ListNode     */    ListNode *reverseKGroup(ListNode *head, int k) {        ListNode *cur = head;        for (int i = 0; i < k; ++i) {            if (!cur) return head;            cur = cur->next;        }        ListNode *new_head = reverse(head, cur);        head->next = reverseKGroup(cur, k);        return new_head;    }    ListNode* reverse(ListNode* head, ListNode* tail) {        ListNode *pre = tail;        while (head != tail) {            ListNode *t = head->next;            head->next = pre;            pre = head;            head = t;        }        return pre;    }};

本文转自博客园Grandyang的博客,原文链接:,如需转载请自行联系原博主。

你可能感兴趣的文章
FASTDFS 安装与开发
查看>>
Building real-time dashboard applications with Apache Flink, Elasticsearch, and Kibana
查看>>
Uncaught SyntaxError: Unexpected token <解决方法
查看>>
【12月06日】A股全市场情绪指标整理分析
查看>>
比特币最好的软件 冷钱包及热钱包
查看>>
jdk动态代理的实现原理
查看>>
MySQL添加数据库的唯一索引的几种方式~
查看>>
(轉貼) 2008年的看我 : C++ 2.0 (C/C++)
查看>>
(C#)Windows Shell 外壳编程系列2 - 解释,从“桌面”开始展开
查看>>
探索Asp.net mvc 的文件上传(由浅入深)
查看>>
Mint14体验报告 接近Windows的Linux
查看>>
Cordova 讲义 1 – 周金根
查看>>
启用IIS的Gzip压缩功能
查看>>
排除“计算机-默认 权限设置未将 COM 服务器应用程序”的错误
查看>>
关于上一个sql优化测试的部分知识
查看>>
WCF服务编程-非WCF应用程序使用WCF服务
查看>>
Word邮件合并-IT男必备技能
查看>>
通过UIImage显示网络图片
查看>>
网络流题目集锦(转)
查看>>
POJ 1080 Human Gene Functions
查看>>