正文
笔试算法题（13）：反转链表 & 左旋转字符串
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
出题：反转链表（递归和非递归解法）；
分析：有递归跟非递归实现，注意对原始链表头节点的处理，因为其他节点都指向下一个节点，其需要指向NULL；
解题：
struct Node {
int v;
Node *next;
};
Node* NonRecursiveListReverse(Node *head) {
if(head == NULL) return NULL;
Node *previous=NULL, *current=head, *temp=NULL;
/**
* 一定需要注意删除原来的结构，不然最后一个指针与倒数第二个指针
* 相互索引，最终导致无限循环索引
* */
//previous->next=NULL; while(current != NULL) {
temp=current->next;
current->next=previous; previous=current;
current=temp;
} return previous;
}
/**
* 调用此方法的时候需要将previous设置成NULL，也就是
* RecursiveListReverse(NULL, head);
* */
Node* RecursiveListReverse(Node *previous, Node *current) {
Node *temp=current->next;
current->next=previous;
if(temp == NULL) return current;
else return RecursiveListReverse(current, temp);
}
出题：左旋转字符串算法，将字符串最左边的k个字符移动到字符串尾部，局部字符相对顺序不变。要求时间复杂度为O（N），空间复杂度为O（1）；
分析：例如：对"abcdef"施用k=3的左旋转之后变成"cdefabc"。本题与19类似，首先进行全局反转，然后利用k的长度分别对两个部分进行反转；
解题：
/**
* 借用之前已经实现的全局翻转函数reverse
* */
void reverse(char* target, int length) {
char temp;
int i;
for(i=;i<length/;i++) {
temp=*(target+i);
*(target+i)=*(target+(length-i-));
*(target+(length-i-))=temp;
}
} void LeftRotate(char *target, int length, int k) {
reverse(target,length);
reverse(target, length-k);
reverse(target+length-k, k);
}
int main() {
char target[]="abcdef";
LeftRotate(target, , );
char *temp=target;
printf("\n%s\n", temp);
return ;
}
笔试算法题（13）：反转链表 & 左旋转字符串的更多相关文章- leetcode题库练习_左旋转字符串
题目:左旋转字符串 字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部.请定义一个函数实现字符串左旋转操作的功能.比如,输入字符串"abcdefg"和数字2,该函数将返 ...
- 九度OJ 1362 左旋转字符串（Move!Move!!Move!!!）【算法】
题目地址:http://ac.jobdu.com/problem.php?pid=1362 题目描述: 汇编语言中有一种移位指令叫做循环左移(ROL),现在有个简单的任务,就是用字符串模拟这个指令的运 ...
- PAT乙级真题及训练题 1025. 反转链表 (25)
PAT乙级真题及训练题 1025. 反转链表 (25) 感觉几个世纪没打代码了,真是坏习惯,调了两小时把反转链表调出来了,心情舒畅. 这道题的步骤 数据输入,数组纪录下一结点及储存值 创建链表并储存上 ...
- 《剑指offer》第五十八题（左旋转字符串）
// 面试题58(二):左旋转字符串 // 题目:字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部. // 请定义一个函数实现字符串左旋转操作的功能.比如输入字符串"abcde ...
- 编程算法 - 左旋转字符串 代码(C)
版权声明:本文为博主原创文章.未经博主同意不得转载. https://blog.csdn.net/u012515223/article/details/37689725 左旋转字符串 代码(C) 本文 ...
- 剑指 Offer 58 - II. 左旋转字符串 + 简单题
剑指 Offer 58 - II. 左旋转字符串 Offer_58_2 题目描述 java代码 package com.walegarrett.offer; /** * @Author WaleGar ...
- 【面试题042】翻转单词顺序VS左旋转字符串
[面试题042]翻转单词顺序VS左旋转字符串 题目一: 输入一个英文句子,反转句子中单词的顺序,但单词内字符的顺序不变.为简单起见,标点符号和普通字母一样处理. 例如输入字符串“I a ...
- 辗转相除法(GCD)求左旋转字符串
本文写于2017-01-18,从老账号迁移到本账号,原文地址:https://www.cnblogs.com/huangweiyang/p/6297874.html 今天在牛客网上做了一道题,题意就是 ...
- 题目1362：左旋转字符串（Move!Move!!Move!!!）
题目1362:左旋转字符串(Move!Move!!Move!!!) 时间限制:2 秒 内存限制:32 兆 特殊判题:否 提交:2306 解决:961 题目描述: 汇编语言中有一种移位指令叫做循环左移( ...
随机推荐- SQL Server查询第31到40条数据
大致分为两种情况:ID连续和ID不连续. 1.ID连续的情况: 2.ID不连续的情况: (1).两次对表查询,效率较低. ID from A) (2).外层查询没有对表A进行查询,效率提高. ID f ...
- DOM事件简介－－摘自admin10000
Click.touch.load.drag.change.input.error.risize — 这些都是冗长的DOM(文档对象模型)事件列表的一部分.事件可以在文档(Document)结构的任何部 ...
- [LeetCode] Remove Duplicates from Sorted List
Given a sorted linked list, delete all duplicates such that each element appear only once. For examp ...
- 记一次在StackOverFlow上问问题的经历
最近一直在做测试方面的事情,被测的一些功能需要连接到FTP服务器上.而我在做本地测试时为了方便,就使用java写了一个简单的ftp服务器,可以在命令行下直接启动运行. 当时在main函数里是这样写的. ...
- PHP API 框架开发的学习
基于互联网的应用正变得越来越普及,在这个过程中,有更多的站点将自身的资源开放给开发者来调用.对外提供的API 调用使得站点之间的内容关联性更强,同时这些开放的平台也为用户.开发者和中小网站带来了更大的 ...
- PHP函数补完：var_export()
var_export() 函数返回关于传递给该函数的变量的结构信息,它和 var_dump() 类似,不同的是其返回的表示是合法的 PHP 代码.var_export必须返回合法的php代码, 也就是 ...
- label_设置行距、字距及计算含有行间距的label高度
// // ViewController.m // CNBlogs // // Created by PXJ on 16/5/27. // Copyright © 2016年 PXJ. All ...
- perl5 第十三章 Perl的面向对象编程
第十三章 Perl的面向对象编程 by flamephoenix 一.模块简介二.Perl中的类三.创建类四.构造函数 实例变量 五.方法六.方法的输出七.方法的调用八.重载九.析构函数十.继承十一. ...
- mysqli_fetch_array() ,mysqli_fetch_assoc()遇到的问题
该函数每运行一次就会读取一行数据. $book1_imgnum="select * from book_img limit 12"; $book1_totalimg=mysqli_ ...
- vue router.push(),router.replace(),router.go()和router.replace后需要返回两次的问题
转载:https://www.cnblogs.com/lwwen/p/7245083.html https://blog.csdn.net/qq_15385627/article/details/83 ...
题目:左旋转字符串 字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部.请定义一个函数实现字符串左旋转操作的功能.比如,输入字符串"abcdefg"和数字2,该函数将返 ...
题目地址:http://ac.jobdu.com/problem.php?pid=1362 题目描述: 汇编语言中有一种移位指令叫做循环左移(ROL),现在有个简单的任务,就是用字符串模拟这个指令的运 ...
PAT乙级真题及训练题 1025. 反转链表 (25) 感觉几个世纪没打代码了,真是坏习惯,调了两小时把反转链表调出来了,心情舒畅. 这道题的步骤 数据输入,数组纪录下一结点及储存值 创建链表并储存上 ...
// 面试题58(二):左旋转字符串 // 题目:字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部. // 请定义一个函数实现字符串左旋转操作的功能.比如输入字符串"abcde ...
版权声明:本文为博主原创文章.未经博主同意不得转载. https://blog.csdn.net/u012515223/article/details/37689725 左旋转字符串 代码(C) 本文 ...
剑指 Offer 58 - II. 左旋转字符串 Offer_58_2 题目描述 java代码 package com.walegarrett.offer; /** * @Author WaleGar ...
[面试题042]翻转单词顺序VS左旋转字符串 题目一: 输入一个英文句子,反转句子中单词的顺序,但单词内字符的顺序不变.为简单起见,标点符号和普通字母一样处理. 例如输入字符串“I a ...
本文写于2017-01-18,从老账号迁移到本账号,原文地址:https://www.cnblogs.com/huangweiyang/p/6297874.html 今天在牛客网上做了一道题,题意就是 ...
题目1362:左旋转字符串(Move!Move!!Move!!!) 时间限制:2 秒 内存限制:32 兆 特殊判题:否 提交:2306 解决:961 题目描述: 汇编语言中有一种移位指令叫做循环左移( ...
- SQL Server查询第31到40条数据
大致分为两种情况:ID连续和ID不连续. 1.ID连续的情况: 2.ID不连续的情况: (1).两次对表查询,效率较低. ID from A) (2).外层查询没有对表A进行查询,效率提高. ID f ...
- DOM事件简介－－摘自admin10000
Click.touch.load.drag.change.input.error.risize — 这些都是冗长的DOM(文档对象模型)事件列表的一部分.事件可以在文档(Document)结构的任何部 ...
- [LeetCode] Remove Duplicates from Sorted List
Given a sorted linked list, delete all duplicates such that each element appear only once. For examp ...
- 记一次在StackOverFlow上问问题的经历
最近一直在做测试方面的事情,被测的一些功能需要连接到FTP服务器上.而我在做本地测试时为了方便,就使用java写了一个简单的ftp服务器,可以在命令行下直接启动运行. 当时在main函数里是这样写的. ...
- PHP API 框架开发的学习
基于互联网的应用正变得越来越普及,在这个过程中,有更多的站点将自身的资源开放给开发者来调用.对外提供的API 调用使得站点之间的内容关联性更强,同时这些开放的平台也为用户.开发者和中小网站带来了更大的 ...
- PHP函数补完：var_export()
var_export() 函数返回关于传递给该函数的变量的结构信息,它和 var_dump() 类似,不同的是其返回的表示是合法的 PHP 代码.var_export必须返回合法的php代码, 也就是 ...
- label_设置行距、字距及计算含有行间距的label高度
// // ViewController.m // CNBlogs // // Created by PXJ on 16/5/27. // Copyright © 2016年 PXJ. All ...
- perl5 第十三章 Perl的面向对象编程
第十三章 Perl的面向对象编程 by flamephoenix 一.模块简介二.Perl中的类三.创建类四.构造函数 实例变量 五.方法六.方法的输出七.方法的调用八.重载九.析构函数十.继承十一. ...
- mysqli_fetch_array() ,mysqli_fetch_assoc()遇到的问题
该函数每运行一次就会读取一行数据. $book1_imgnum="select * from book_img limit 12"; $book1_totalimg=mysqli_ ...
- vue router.push(),router.replace(),router.go()和router.replace后需要返回两次的问题
转载:https://www.cnblogs.com/lwwen/p/7245083.html https://blog.csdn.net/qq_15385627/article/details/83 ...
