leetcode_25_Reverse Nodes in k-Group

欢迎大家阅读参考,如有错误或疑问请留言纠正,谢谢

Reverse Nodes in k-Grou

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

class Solution {
//once the link order of the list is changed,
//we must keep the previous pointer(p in the code) updated, if we want to use it agian
public:
	void reverse_range(ListNode* prev, ListNode* end, ListNode*& p)
	{
		ListNode* last = prev->next;
		ListNode* cur = last->next;
		while(cur != end)
		{
			last->next = cur->next;
			cur->next = prev->next;
			prev->next = cur;

			cur = last->next;
		}
		p = last;
	}
	ListNode *reverseKGroup(ListNode *head, int k)
	{
		if(k <= 1) return head;
		ListNode *dummy = new ListNode(-1);
		dummy->next = head;
		ListNode* prev = dummy;
		ListNode* p = dummy->next;
		int cnt = 1;
		while(p != NULL)
		{
			if(cnt%k == 0)
			{
				reverse_range(prev, p->next, p);//update p is very important
				prev = p;
			}
			p = p->next;
			cnt++;
		}
		return dummy->next;
	}
};
#include<iostream>

using namespace std;

#define N 5

struct ListNode {
	int val;
	ListNode *next;
	ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
//once the link order of the list is changed,
//we must keep the previous pointer(p in the code) updated, if we want to use it agian
public:
	void reverse_range(ListNode* prev, ListNode* end, ListNode*& p)
	{
		ListNode* last = prev->next;
		ListNode* cur = last->next;
		while(cur != end)
		{
			last->next = cur->next;
			cur->next = prev->next;
			prev->next = cur;

			cur = last->next;
		}
		p = last;
	}
	ListNode *reverseKGroup(ListNode *head, int k)
	{
		if(k <= 1) return head;
		ListNode *dummy = new ListNode(-1);
		dummy->next = head;
		ListNode* prev = dummy;
		ListNode* p = dummy->next;
		int cnt = 1;
		while(p != NULL)
		{
			if(cnt%k == 0)
			{
				reverse_range(prev, p->next, p);//update p is very important
				prev = p;
			}
			p = p->next;
			cnt++;
		}
		return dummy->next;
	}
};

ListNode *creatlist()
{
	ListNode *head = NULL;
	ListNode *p;
	for(int i=0; i<N; i++)
	{
		int a;
		cin>>a;
		p = (ListNode*) malloc(sizeof(ListNode));
		p->val = a;
		p->next = head;
		head = p;
	}
	return head;
}

int main()
{
	ListNode *list = creatlist();
	Solution lin;
	int a;
	cin>>a;
	ListNode *outlist = lin.reverseKGroup ( list,a );
	for(int i=0; i<N; i++)
	{
		cout<<outlist->val;
		outlist = outlist->next;
	}
}
时间: 02-14

leetcode_25_Reverse Nodes in k-Group的相关文章

udev规则以及编写

主要内容: udev简介 如何配置和使用udev 如何编写udev规则 字符串替换和匹配 udev主要作用 编写udev规则实例 1. udev简介 1.1 什么是udev? udev是Linux(linux2.6内核之后)默认的设备管理工具.udev 以守护进程的形式运行,通过侦听内核发出来的 uevent 来管理 /dev目录下的设备文件. 如何理解udev是守护进程呢?即系统内核启动后init进程(比如busybox的init程序.sysinit.Upstart或systemd)根据run

并查集应用

题目描述: One way that the police finds the head of a gang is to check people's phone calls. If there is a phone call between A and B, we say that A and B is related. The weight of a relation is defined to be the total time length of all the phone calls

k-近邻算法学习

参考: http://blog.csdn.net/tjusxh/article/details/51052319 k-近邻算法:简单地说就是采用测量不同特征值之间的距离进行分类的方法. 三个基本要素:K值的选择.距离度量.分类决策规则 优点:精度高.对异常值不敏感.无数据输入假定. 缺点:计算复杂度高.空间复杂度高. kNN算法的一般流程: 1.导入数据 2.为保证特征权重相同,进行数值归一化 3.距离计算 4.对距离进行排序,选择前K个距离,求出标签出现最多的类别 #include<iostr

python groupby

groupby() 将key函数作用于原循环器的各个元素.根据key函数结果,将拥有相同函数结果的元素分到一个新的循环器.每个新的循环器以函数返回结果为标签. 这就好像一群人的身高作为循环器.我们可以使 用这样一个key函数: 如果身高大于180,返回"tall":如果身高底于160,返回"short";中间的返回"middle".最终,所有身高将分为三个循环器, 即"tall", "short", &qu

POJ 1724 ROADS

点击打开链接 ROADS Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 10202   Accepted: 3786 Description N cities named with numbers 1 ... N are connected with one-way roads. Each road has two parameters associated with it : the road length and t

深度学习在graph上的使用

本文要介绍的这一篇paper是ICML2016上一篇关于 CNN 在图(graph)上的应用.ICML 是机器学习方面的顶级会议,这篇文章--<< Learning CNNs for Graphs>>--所研究的内容也具有非常好的理论和实用的价值.如果您对于图的数据结构并不是很熟悉建议您先参考本文末的相关基础知识的介绍. CNN已经在计算机视觉(CV)以及自然语言处理等领域取得了state-of-art 的水平,其中的数据可以被称作是一种Euclidean Data,CNN正好能够

udev

如果你使用Linux比较长时间了,那你就知道,在对待设备文件这块,Linux改变了几次策略.在Linux早期,设备文件仅仅是是一些带有适当的属性集的普通文件,它由mknod命令创建,文件存放在/dev目录下.后来,采用了devfs, 一个基于内核的动态设备文件系统,他首次出现在2.3.46内核中.Mandrake,Gentoo等Linux分发版本采用了这种方式.devfs创建 的设备文件是动态的.但是devfs有一些严重的限制,从2.6.13版本后移走了.目前取代他的便是文本要提到的udev--

深入排序算法的多语言实现

深入浅出排序算法的多语言实现 作者:白宁超 2015年10月8日20:08:11 摘要:十一假期于实验室无趣,逐研究起数据结构之排序.起初觉得就那么几种排序,两三天就搞定了,后来随着研究的深入,发觉里面有不少东西.本文介绍常用的排序算法,主要从以下几个方面:算法的介绍.算法思想.算法步骤.算法优缺点.算法实现.运行结果.算法优化等.最后对本文进行总结.本文为作者原创,程序经测试无误.部分资料引用论文和网络材料以及博客,后续参见参考文献.(本文原创,转载注明出处) 1 排序的基本概念 排序: 所谓

使用C# 和Consul进行分布式系统协调

使用C# 和Consul进行分布式系统协调 随着大数据时代的到来,分布式是解决大数据问题的一个主要手段,随着越来越多的分布式的服务,如何在分布式的系统中对这些服务做协调变成了一个很棘手的问题.今天我们就来看看如何使用C# ,利用开源对分布式服务做协调. 在对分布式的应用做协调的时候,主要会碰到以下的应用场景: 业务发现(service discovery) 找到分布式系统中存在那些可用的服务和节点 名字服务 (name service) 通过给定的名字知道到对应的资源 配置管理 (configu

UVA 714 二分最大化最小值

题意:输入t表示有多个样例,输入n,group表示有n个数分为group组使每组和最小 #include<iostream> #include<string.h> using namespace std; #define ll long long const int N = 500 + 5; ll a[N]; int vis[N]; ll num,m,group; int solve(int d) { ll sum=0; int k=1; for(int i=0;i<num;