博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
【LeetCode】25. Reverse Nodes in k-Group (2 solutions)
阅读量:5880 次
发布时间:2019-06-19

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

Reverse Nodes in k-Group

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.

For 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

 

解法一:

看到逆序,第一反应就是栈。

使用栈,每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) {        ListNode* newhead = new ListNode(-1);        ListNode* tail = newhead;        ListNode* begin = head;        ListNode* end = begin;        while(true)        {            int count = k;            while(count && end != NULL)            {                end = end->next;                count --;            }            if(count == 0)            {
//reverse from [begin, end) stack
s; while(begin != end) { s.push(begin); begin = begin->next; } while(!s.empty()) { ListNode* top = s.top(); s.pop(); tail->next = top; tail = tail->next; } } else {
//leave out tail->next = begin; break; } } return newhead->next; }};

 

解法二:

自定义函数reverse(begin, end)

对[begin, end]范围内实现逆序,并且更新begin, end

逐k次调用即可。

注意:

(1)由于需要更新begin, end,因此参数形式为ListNode*&

(2)在[begin,end]范围内实现逆序之后,需要链如原先的链表,不可脱离

/** * 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) {        if(head == NULL)            return NULL;        if(k == 1)        //no swap            return head;                    int i = 1;        //head node        ListNode* newhead = new ListNode(-1);        newhead->next = head;        ListNode* tail = newhead;                ListNode* begin = head;        ListNode* end = begin;        while(end != NULL)        {            if(i%k == 0)            {                reverse(begin, end);                tail->next = begin;                tail = end;                //new begin                begin = end->next;            }            end = end->next;            i ++;        }        return newhead->next;    }    void reverse(ListNode*& begin, ListNode*& end)    {
//reverse the list. begin points to new begin, end points to new end if(begin == end) {
//only one node return; } else if(begin->next == end) {
//two nodes begin->next = end->next; end->next = begin; //swap begin and end ListNode* temp = begin; begin = end; end = temp; } else {
//at least three nodes ListNode* pre = begin; ListNode* cur = pre->next; ListNode* post = cur->next; while(post != end->next) { cur->next = pre; pre = cur; cur = post; post = post->next; } cur->next = pre; //old begin points to the new end end = begin; end->next = post; //cur points to the old end begin = cur; } }};

转载地址:http://aqdix.baihongyu.com/

你可能感兴趣的文章
VUEJS开发规范
查看>>
Android系统的创世之初以及Activity的生命周期
查看>>
彻底解决Linux下memcached的安装
查看>>
人人都会数据采集- Scrapy 爬虫框架入门
查看>>
Android网络编程11之源码解析Retrofit
查看>>
apache .htaccess 文件配置记录
查看>>
我的全站https之路
查看>>
不使用三方包时,如何在社交系统ThinkSNS中建立优雅的用户权限管理【研发日记13】...
查看>>
学会使用npm脚本
查看>>
前端面试之htm5新特性
查看>>
实现atoi函数(string转integer)
查看>>
虚拟机编译安装lnmp(centos7,nginx1.12.0,MariaDB 10.2,php-7.1.6)
查看>>
Java IO学习笔记三
查看>>
JS 原型的解释
查看>>
Yii2中你可能忽略但很有用的两个方法batch&each
查看>>
高程(第二章) 在HTML中使用JavaScript
查看>>
CSS选择器总结(分类、优先级)
查看>>
Hibernate4与Spring4集成
查看>>
React-Simple-Form轮子第一版释出
查看>>
Java 集合框架浅析
查看>>