#面试题集锦#实现单链表反转

zkbhj 发表了文章 • 0 个评论 • 142 次浏览 • 2020-08-14 17:16 • 来自相关话题

反转一个链表

示例:输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
结构体定义struct ListNode {
int val;
struct ListNode *next;
};
 





 思路一

先对原链表做头删操作,再对新链表做头插
定义一个新head头指针,标记为newHead,将它初始为NULL,并非指向NULL,最后我们选择返回这个newHead指针作为新链表的头指针。
定义一个结点node作为"临时中转站",初始化与否并无大影响。进行循环遍历链表各个结点,判定head指针是否为空,即是否到达了原链表的结尾。如果不为空,说明还没有到达尾部。如果程序第一次运行就没有进入循环,说明传入了一个空链表,此时返回newHead新链表的头指针,同样返回NULL,这样处理也是合理的。以下开始逆序链表逻辑:在当前指针不为NULL时,先对原链表做头删操作,再对新链表做头插操作。即使用循环进行操作:让node指针指向传入函数链表的头指针head,两指针指向保持相同。然后让head指针指向它的next结点,此时旧链表已经完成了头删操作。第一个结点已经被"切割"下来。接下来要做的就是对新链表进行头插操作,使结点放入新链表。让node指针的next下一个结点指向新链表的头指针newHead,完成结点的链接,即头插入新的链表中。然后更新newHead指向为新链表的头结点。进行下一次循环。最终head指针指向了原链表的结尾,即为NULL,退出循环,此时新链表已经反转完毕,情况如图:最终返回新链表头指针newHead即可。





 struct ListNode *reverseList(struct ListNode* head) {
struct ListNode *newHead = NULL;
struct ListNode *node;
while (head != NULL) {
//1. 对之前的链表做头删
node = head;
head = head->next;

//2. 对新链表做头插
node->next = newHead;
newHead = node;
}
return newHead;
}
思路二





利用选择语句,找到空链表的情况,此情况返回NULL空指针,因为空链表不能反转,或者说反转之后还是一个空链表,返回空。利用三个指针p0"前指针"、p1“当前指针”、p2"后指针"来分批处理链表元素,p0置为NULL,它将作为链表的尾结点向前推进处理,p1指向旧链表的头指针head,p2指向旧链表的头指针的next结点。开始遍历链表,循环判定因子为p1,当它为空时到达链表尾部跳出循环。否则在表中执行循环内逻辑:将p1指向的当前结点的下一个结点指向p0,即前一个结点。此时p0为NULL,那么p1的下一个结点就为空了,它现在是最后一个结点。然后将p0指针指向p1,将p1指针指向p2,注意这两步不可以调换顺序,否则正确向后挪移一位。此时完成了三个指针的一轮更迭。判定p2指针是否为空,如果为空说明此时p2到达了链表结尾,当前指针p1的指向为最后一个结点,它的next即为空。如果不为空,将p2更新到下一个结点,进行下一次循环。下一次进行循环时,就会把截断结点链接到新链表的头部,同时更新三个指针。继续循环。循环终止条件为:p1指向了链表尾部的NULL,此时p1的前指针p0即指向了反转后的链表,它就是新链表的head头指针。此时返回p0即可。





 struct ListNode *reverseList(struct ListNode* head) {
if (head == NULL) {
return NULL;
}
struct ListNode *p0 = NULL;
struct ListNode *p1 = head;
struct ListNode *p2 = head->next;
while (p1 != NULL) {
p1->next = p0;

p0 = p1;
p1 = p2;
if (p2 != NULL) {
p2 = p2->next;
}
}
return p0;
}
参考文档:
https://blog.csdn.net/qq_42351880/article/details/88637387
 
  查看全部
反转一个链表

示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

结构体定义
struct ListNode {
int val;
struct ListNode *next;
};

 

QQ截图20200814170600.jpg

 思路一

先对原链表做头删操作,再对新链表做头插
  1. 定义一个新head头指针,标记为newHead,将它初始为NULL,并非指向NULL,最后我们选择返回这个newHead指针作为新链表的头指针。

  1. 定义一个结点node作为"临时中转站",初始化与否并无大影响。
  2. 进行循环遍历链表各个结点,判定head指针是否为空,即是否到达了原链表的结尾。如果不为空,说明还没有到达尾部。如果程序第一次运行就没有进入循环,说明传入了一个空链表,此时返回newHead新链表的头指针,同样返回NULL,这样处理也是合理的。
  3. 以下开始逆序链表逻辑:在当前指针不为NULL时,先对原链表做头删操作,再对新链表做头插操作。即使用循环进行操作:
  4. 让node指针指向传入函数链表的头指针head,两指针指向保持相同。
  5. 然后让head指针指向它的next结点,此时旧链表已经完成了头删操作。第一个结点已经被"切割"下来。接下来要做的就是对新链表进行头插操作,使结点放入新链表。
  6. 让node指针的next下一个结点指向新链表的头指针newHead,完成结点的链接,即头插入新的链表中。然后更新newHead指向为新链表的头结点。进行下一次循环。
  7. 最终head指针指向了原链表的结尾,即为NULL,退出循环,此时新链表已经反转完毕,情况如图:
  8. 最终返回新链表头指针newHead即可。


QQ截图20200814170610.jpg

 
struct ListNode *reverseList(struct ListNode* head) {
struct ListNode *newHead = NULL;
struct ListNode *node;
while (head != NULL) {
//1. 对之前的链表做头删
node = head;
head = head->next;

//2. 对新链表做头插
node->next = newHead;
newHead = node;
}
return newHead;
}

思路二

QQ截图20200814171211.jpg

  1. 利用选择语句,找到空链表的情况,此情况返回NULL空指针,因为空链表不能反转,或者说反转之后还是一个空链表,返回空。
  2. 利用三个指针p0"前指针"、p1“当前指针”、p2"后指针"来分批处理链表元素,p0置为NULL,它将作为链表的尾结点向前推进处理,p1指向旧链表的头指针head,p2指向旧链表的头指针的next结点。
  3. 开始遍历链表,循环判定因子为p1,当它为空时到达链表尾部跳出循环。否则在表中执行循环内逻辑:将p1指向的当前结点的下一个结点指向p0,即前一个结点。此时p0为NULL,那么p1的下一个结点就为空了,它现在是最后一个结点。
  4. 然后将p0指针指向p1,将p1指针指向p2,注意这两步不可以调换顺序,否则正确向后挪移一位。此时完成了三个指针的一轮更迭。
  5. 判定p2指针是否为空,如果为空说明此时p2到达了链表结尾,当前指针p1的指向为最后一个结点,它的next即为空。如果不为空,将p2更新到下一个结点,进行下一次循环。
  6. 下一次进行循环时,就会把截断结点链接到新链表的头部,同时更新三个指针。继续循环。
  7. 循环终止条件为:p1指向了链表尾部的NULL,此时p1的前指针p0即指向了反转后的链表,它就是新链表的head头指针。此时返回p0即可。


QQ截图20200814171221.jpg

 
struct ListNode *reverseList(struct ListNode* head) {
if (head == NULL) {
return NULL;
}
struct ListNode *p0 = NULL;
struct ListNode *p1 = head;
struct ListNode *p2 = head->next;
while (p1 != NULL) {
p1->next = p0;

p0 = p1;
p1 = p2;
if (p2 != NULL) {
p2 = p2->next;
}
}
return p0;
}

参考文档:
https://blog.csdn.net/qq_42351880/article/details/88637387
 
 

面试初中级开发工程师需要注意的方面

zkbhj 发表了文章 • 0 个评论 • 731 次浏览 • 2017-02-17 10:15 • 来自相关话题

1、逻辑思维能力:抛出一个场景,让面试者思考如何实现,从中提出问题,考察面试者的逻辑思维能力;
2、学习能力:从学历、意愿、自己的项目(github\blog),是否经常参加社团活动、是否经常阅读技术书籍,已经自驱能力等;
3、成长规划:对自己的定位、最近一年的规划计划;
4、基本技能:PHP基本技能、前端、服务器、缓存、数据库、设计模式、工具使用、框架等;
5、沟通能力:职业经历中遇到的通过自己的努力解决问题的事情;面试过程中的说话谈吐;
6、
  查看全部
1、逻辑思维能力:抛出一个场景,让面试者思考如何实现,从中提出问题,考察面试者的逻辑思维能力;
2、学习能力:从学历、意愿、自己的项目(github\blog),是否经常参加社团活动、是否经常阅读技术书籍,已经自驱能力等;
3、成长规划:对自己的定位、最近一年的规划计划;
4、基本技能:PHP基本技能、前端、服务器、缓存、数据库、设计模式、工具使用、框架等;
5、沟通能力:职业经历中遇到的通过自己的努力解决问题的事情;面试过程中的说话谈吐;
6、
 

PHP中级程序员常见面试题

zkbhj 发表了文章 • 0 个评论 • 757 次浏览 • 2017-02-15 10:08 • 来自相关话题

写一个函数,尽可能高效的,从一个标准url里取出文件的扩展名例如: http://www.test.com.cn/abc/de/fg.php?id=1需要取出php或.php

答: 1、$a="http://www.test.com.cn/abc/de/fg.php?id=1";    

2、$b=parse_url($a);

3、Echosubstr($b['path'],strpos($b['path'],'.')); 或者:

4、Echoend(explode('.',$b['path']));2


描述一下大流量高并发量网站的解决方案


答: 1、确认服务器硬件是否足够支持当前的流量。


2、使用memcache缓存技术,将动态数据缓存到内存中,动态网页直接调用这些文件,而不必在访问数据库。


3、禁止外部的盗链。


4、外部网站的图片或者文件盗链往往会带来大量的负载压力,因此应该严格限制外部对自身图片或者文件盗链,目前可以简单的通过refer来控制盗 链,apache自己就可以通过配置来禁止盗链。


5、控制大文件的下载。 大文件的下载会占用很大的流量,对于非SCSI硬盘来说会消耗,使得网站响应能力下降。


6、使用不同的主机分流主要流量


7、使用流量统计软件。 在网站上安装一个流量统计软件,可以即时知道哪些地方耗费了大量流量,哪些页面需要再进行优化。


8、分库分表。


9、Sphinx全文索引引擎。


如何设计或配置Mysql,才能达到高效使用的目的。


答:


1、数据库设计方面,设计结构良好的数据库,允许部分数据冗余。 选取最适用的字段属性,尽可能把字段设置为NOTNULL,这样在查询的时候,数据库不用去比较NULL值。


2、系统架构设计方面,表散列,把海量数据散列到几个不同的表里面,集群,数据库查询和写入分开。 写高效sql语句,以提高效率。使用连接(join)来代替子查询使用联合(union)来代替手动创建的临时表所得皆必须,只从数据库取必须的数据。必 要的时候用不同的存储引擎,比如Innodb可以减少死锁,HEAP可以提高一个数量级的查询速度。


使用事务使用外键使用索引24.如何进行防SQL注 入?


答:


1、过滤掉一些常见的数据库操作关键字:select,insert,update,delete,and,*等或者通过系统函 数:addslashes(需要被过滤的内容)来进行过滤。


2、在PHP配置文件中Register_globals=off;设置为关闭状态 //作用将注册全局变量关闭。比如:接收POST表单的值使用$_POST['user'],如果将register_globals=on;直接使 用$user可以接收表单的值。


3、SQL语句书写的时候尽量不要省略小引号(tab键上面那个)和单引号


4、提高数据库命名技巧,对于一些重要的字段根据程序的特点命名,取不易被猜到的


5、对于常用的方法加以封装,避免直接暴漏SQL语句


6、开启PHP安全模式Safe_mode=on;


7、打开magic_quotes_gpc来防止SQL注入 Magic_quotes_gpc=off;默认是关闭的,它打开后将自动把用户提交的sql语句的查询进行转换,把'转为\',这对防止sql注入有重 大作用。因此开启:magic_quotes_gpc=on;


8、控制错误信息关闭错误提示信息,将错误信息写到系统日志。


9、使用mysqli或pdo预处理。


用PHP写出一个安全的用户登录系统需要注意哪些方面。


答:


1、密码要使用MD5(密码+字符串)进行加 密。


2、登录表单的名称不要跟数据库字段一样,以免暴漏表字段。


3、用户表的表名、字段名、密码尽量用不容易被猜到的。


4、要使用验证码验证登陆,以防止 暴力破解。


5、验证提交的数据是不是来自本网站。


6、登录后台处理代码数据库部分使用预处理,做好过滤,防止sql注入。


使用过哪些PHP框架。试 描述其优劣点。


答:


1、BroPHP框架:优点:轻量级学习型框架,配置简单,操作简单,容易上手,提供了比较全面的文档。缺点:


2、ThinkPHP框 架:优点:功能比较全面,配置相对比较简单,操作相对比较简单,有很多使用示例程序。缺点:提供的操作方法太多,新手不知如何选择,文档不够全面。


用过哪些版本控制工具?


答:使用过SVN版本控制器。


输出为Mozilla/4.0(compatible;MSIE5.01;Window NT 5.0)时,可能的输出语句是:B


A.$_SERVER['HTTP_USER_AGENT_TYPE'];


B. $_SERVER['HTTP_USER_AGENT'];


C. $_SERVER['USER_AGENT'];


D. $_SERVER['AGENT'];


下面功能PHP无法实现的是:D


A. 服务器端脚本运行


B. 命令行脚本运行


C. 客户端图形界面(GUI)程序


D. 浏览器端执行DOM操作


下面说法不正确的是:C


A. PHP有四种标量类型:布尔型(boolean),整型(integer),浮点型(float),字符串(string)


B. 浮点型(float)与双精度型(double)是同一种类型


C. 符合类型包括:数组(array),对象(object),资源(resource)


D. 伪类型:混合型(mixed),数字型(number),回调(callback)


下面不是PHP语法的组成部分的函数是:AD


A. array B. eval C. each D. list


执行下面的代码的结果是什么?A


A. boolean


B. boolean0


C. booleanFALSE


D. booleanfalse


SESSION与 COOKIE的区别是什么,请从协议,产生的原因与作用说明?


答:
1、http无状态协议,不能区分用户是否是从同一个网站上来的,同一个用户请求不同的 页面不能看做是同一个用户。


2、SESSION保存在服务器端,COOKIE保存在客户端,SESSION依赖COOKIE进行传输,如果COOKIE被 禁用了,SESSION将不能继续使用。


HTTP状态中302、403、 500代码含义?


答:


300重定向、403服务器拒绝访问、500服务器内部错误。


Linux 下建立压缩包,解压缩包的命令。


答:
1、压缩:gzip 、tar -cvfz、zip、bzip22、解压:gunzip、tar -zxvf、unzip、bunzip2
$a=3;$b=4; if($a||$b=5){ ||或和|的区别 echo 'todo'; } $b的值是(a):
A a. 4; b. 5; c. 3; d. false


什么是面向对象?主要特征是什么?


答:
1、面向对象是程序的一种设计方式,它利于提高程序的重用性,是程序结构更加清晰。
2、主要特征:封装、继承、多态。 查看全部
写一个函数,尽可能高效的,从一个标准url里取出文件的扩展名例如: http://www.test.com.cn/abc/de/fg.php?id=1需要取出php或.php

答: 1、$a="http://www.test.com.cn/abc/de/fg.php?id=1";    

2、$b=parse_url($a);

3、Echosubstr($b['path'],strpos($b['path'],'.')); 或者:

4、Echoend(explode('.',$b['path']));2


描述一下大流量高并发量网站的解决方案


答: 1、确认服务器硬件是否足够支持当前的流量。


2、使用memcache缓存技术,将动态数据缓存到内存中,动态网页直接调用这些文件,而不必在访问数据库。


3、禁止外部的盗链。


4、外部网站的图片或者文件盗链往往会带来大量的负载压力,因此应该严格限制外部对自身图片或者文件盗链,目前可以简单的通过refer来控制盗 链,apache自己就可以通过配置来禁止盗链。


5、控制大文件的下载。 大文件的下载会占用很大的流量,对于非SCSI硬盘来说会消耗,使得网站响应能力下降。


6、使用不同的主机分流主要流量


7、使用流量统计软件。 在网站上安装一个流量统计软件,可以即时知道哪些地方耗费了大量流量,哪些页面需要再进行优化。


8、分库分表。


9、Sphinx全文索引引擎。


如何设计或配置Mysql,才能达到高效使用的目的。


答:


1、数据库设计方面,设计结构良好的数据库,允许部分数据冗余。 选取最适用的字段属性,尽可能把字段设置为NOTNULL,这样在查询的时候,数据库不用去比较NULL值。


2、系统架构设计方面,表散列,把海量数据散列到几个不同的表里面,集群,数据库查询和写入分开。 写高效sql语句,以提高效率。使用连接(join)来代替子查询使用联合(union)来代替手动创建的临时表所得皆必须,只从数据库取必须的数据。必 要的时候用不同的存储引擎,比如Innodb可以减少死锁,HEAP可以提高一个数量级的查询速度。


使用事务使用外键使用索引24.如何进行防SQL注 入?


答:


1、过滤掉一些常见的数据库操作关键字:select,insert,update,delete,and,*等或者通过系统函 数:addslashes(需要被过滤的内容)来进行过滤。


2、在PHP配置文件中Register_globals=off;设置为关闭状态 //作用将注册全局变量关闭。比如:接收POST表单的值使用$_POST['user'],如果将register_globals=on;直接使 用$user可以接收表单的值。


3、SQL语句书写的时候尽量不要省略小引号(tab键上面那个)和单引号


4、提高数据库命名技巧,对于一些重要的字段根据程序的特点命名,取不易被猜到的


5、对于常用的方法加以封装,避免直接暴漏SQL语句


6、开启PHP安全模式Safe_mode=on;


7、打开magic_quotes_gpc来防止SQL注入 Magic_quotes_gpc=off;默认是关闭的,它打开后将自动把用户提交的sql语句的查询进行转换,把'转为\',这对防止sql注入有重 大作用。因此开启:magic_quotes_gpc=on;


8、控制错误信息关闭错误提示信息,将错误信息写到系统日志。


9、使用mysqli或pdo预处理。


用PHP写出一个安全的用户登录系统需要注意哪些方面。


答:


1、密码要使用MD5(密码+字符串)进行加 密。


2、登录表单的名称不要跟数据库字段一样,以免暴漏表字段。


3、用户表的表名、字段名、密码尽量用不容易被猜到的。


4、要使用验证码验证登陆,以防止 暴力破解。


5、验证提交的数据是不是来自本网站。


6、登录后台处理代码数据库部分使用预处理,做好过滤,防止sql注入。


使用过哪些PHP框架。试 描述其优劣点。


答:


1、BroPHP框架:优点:轻量级学习型框架,配置简单,操作简单,容易上手,提供了比较全面的文档。缺点:


2、ThinkPHP框 架:优点:功能比较全面,配置相对比较简单,操作相对比较简单,有很多使用示例程序。缺点:提供的操作方法太多,新手不知如何选择,文档不够全面。


用过哪些版本控制工具?


答:使用过SVN版本控制器。


输出为Mozilla/4.0(compatible;MSIE5.01;Window NT 5.0)时,可能的输出语句是:B


A.$_SERVER['HTTP_USER_AGENT_TYPE'];


B. $_SERVER['HTTP_USER_AGENT'];


C. $_SERVER['USER_AGENT'];


D. $_SERVER['AGENT'];


下面功能PHP无法实现的是:D


A. 服务器端脚本运行


B. 命令行脚本运行


C. 客户端图形界面(GUI)程序


D. 浏览器端执行DOM操作


下面说法不正确的是:C


A. PHP有四种标量类型:布尔型(boolean),整型(integer),浮点型(float),字符串(string)


B. 浮点型(float)与双精度型(double)是同一种类型


C. 符合类型包括:数组(array),对象(object),资源(resource)


D. 伪类型:混合型(mixed),数字型(number),回调(callback)


下面不是PHP语法的组成部分的函数是:AD


A. array B. eval C. each D. list


执行下面的代码的结果是什么?A


A. boolean


B. boolean0


C. booleanFALSE


D. booleanfalse


SESSION与 COOKIE的区别是什么,请从协议,产生的原因与作用说明?


答:
1、http无状态协议,不能区分用户是否是从同一个网站上来的,同一个用户请求不同的 页面不能看做是同一个用户。


2、SESSION保存在服务器端,COOKIE保存在客户端,SESSION依赖COOKIE进行传输,如果COOKIE被 禁用了,SESSION将不能继续使用。


HTTP状态中302、403、 500代码含义?


答:


300重定向、403服务器拒绝访问、500服务器内部错误。


Linux 下建立压缩包,解压缩包的命令。


答:
1、压缩:gzip 、tar -cvfz、zip、bzip22、解压:gunzip、tar -zxvf、unzip、bunzip2
$a=3;$b=4; if($a||$b=5){ ||或和|的区别 echo 'todo'; } $b的值是(a):
A a. 4; b. 5; c. 3; d. false


什么是面向对象?主要特征是什么?


答:
1、面向对象是程序的一种设计方式,它利于提高程序的重用性,是程序结构更加清晰。
2、主要特征:封装、继承、多态。

关于面试的一些总结

zkbhj 发表了文章 • 0 个评论 • 820 次浏览 • 2017-02-15 10:04 • 来自相关话题

【作为一名面试官】
面试应该善于发现他所善长的东西,还有你得清楚你的项目具体需要哪些能力的人(比如在一个普通团队项目中,我非常看重一个人对一个需求解耦/框架/模式的理解,我可不愿意要一个进来把我的代码搞乱套的人).而不是他知道多少晦涩的语法和他不曾知道的技巧。
【作为一名面试官】
面试应该善于发现他所善长的东西,还有你得清楚你的项目具体需要哪些能力的人(比如在一个普通团队项目中,我非常看重一个人对一个需求解耦/框架/模式的理解,我可不愿意要一个进来把我的代码搞乱套的人).而不是他知道多少晦涩的语法和他不曾知道的技巧。