&nbsp>&nbsp
&nbsp>&nbsp
&nbsp>&nbsp
Linux下的C语言编程&&头插法建立单链表
摘要：建立一个带有头结点的单向链表,并将存储在数组中的字符依次转储到链表的各个结点中。#include&stdio.h&#include&stdlib.h&structnode//瀹氫箟涓EUR涓?粨鏋勪綋{structnode*};typedefstructnodeNtypedefstructnode*Lintinit(Link*head)//鍒濆?鍖栭摼琛?{*head=(Link)malloc(sizeof(No
建立一个带有头结点的单向链表,并将存储在数组中的字符依次转储到链表的各个结点中。
#include &stdio.h&#include &stdlib.h&struct node//瀹氫箟涓EUR涓?粨鏋勪綋{ struct node *};typedef struct node Ntypedef struct node * Lint init(Link *head)//鍒濆?鍖栭摼琛?{ *head = (Link)malloc(sizeof(Node)); if(!(*head))//鍒嗛厤涓嶆垚鍔熷氨閫EUR鍑? { printf(&error!/n&); return 0; } (*head)-&next = NULL; return 1;}void insert_head(Link *head,int n,int b[])//澶存彃娉?{ L *head = (Link)malloc(sizeof(Node)); if(!(*head)) { printf(&error!/n&); exit(-1); } (*head)-&next = NULL; for(i = 0; i & i++)//鏍稿績浠g爜锛屽皢鏁扮粍b鐨勫厓绱犳彃鍏? { p = (Link)malloc(sizeof(Node)); p-&num = b[i]; p-&next = (*head)-& (*head)-&next = }}void display(Link head)//閬嶅巻閾捐〃{ Link p = head-& while(p != NULL) { printf(&%d&,p-&num); p = p-& } printf(&/n&);}int main(){ Link head = NULL; int b[10]; printf(&input the arry!/n&); for(i = 0; i & 10; i++) { scanf(&%d&,&;b[i]); } init(&;head); insert_head(&;head,10,b); display(head); return 0;}
以上是的内容，更多
的内容，请您使用右上方搜索功能获取相关信息。
若你要投稿、删除文章请联系邮箱：zixun-group@service.aliyun.com,工作人员会在五个工作日内给你回复。
云服务器 ECS
可弹性伸缩、安全稳定、简单易用
&40.8元/月起
预测未发生的攻击
&24元/月起
为您提供0门槛上云实践机会
你可能还喜欢
你可能感兴趣
阿里云教程中心为您免费提供
Linux下的C语言编程&&头插法建立单链表相关信息，包括
的信息，所有Linux下的C语言编程&&头插法建立单链表相关内容均不代表阿里云的意见！投稿删除文章请联系邮箱：zixun-group@service.aliyun.com，工作人员会在五个工作日内答复
售前咨询热线
支持与服务
资源和社区
关注阿里云
International程序员面试之算法备忘录（三） | 链表 - 简书
程序员面试之算法备忘录（三） | 链表
本文是题主准备面试时记录下的笔记整理而来，稍显粗陋，还请各位撸友勿喷哈！
熟练使用常用数据结构的基本操作
加深对常用算法与技巧的理解
《程序员面试金典》
《剑指offer》
《结构之法 --July》
1_1.removeDuplicateFromLinklist
1.问题描述
未排序链表
移除重复节点
2.策略一：
对链表排序
通过快慢指针消除重复元素
3.策略二：
哈希表储存元素
遇到重复元素，从链表中删去.
4.注意指针的命名方式
5.代码示例：
/*************************************************************************
& File Name:
Solution.h
& Description:
（1）问题描述
A.已排序链表
B.移除重复节点
& Conclusion:
（1）策略一：
A.链表排序
B.通过快慢指针消除重复元素
（2）策略二：
A.哈希表储存元素
B.遍历链表
C.遇到重复元素，从链表中删去.
rh_Jameson
& Created Time:
日 星期二 11时36分52秒
************************************************************************/
#ifndef _SOLUTION_H
#define _SOLUTION_H
#include&iostream&
#include&string&
#include&algorithm&
#include&map&
#include&cstdlib&
#include&ctime&
#include "LinkList.h"
class Solution {
//=================哈希实现：空间O（M）,时间O（N）====================//
void removeDuplicatesFromLinklistByHash(ListNode *head){
if(head == NULL){
cout && "空链表" &&
//哈希实现
map&int, int& unique_
ListNode *p = head, *tmp = new ListNode(0);
ListNode *q = head-&
unique_map[p-&val] = p-&
for(q = head-& q != NULL; q = q-&next){
if(unique_map.count(q-&val)){
p-&next = q-&
unique_map[q-&val] = q-&
//===================while形式====================//
while(q != NULL){
if(unique_map.count(q-&val)){
p-&next = q-&
unique_map[q-&val] = q-&
//=================================两个指针实现版=======================================//
ListNode *deleteDuplicates(ListNode *head) {
//头结点是第一个结点
if(head == NULL){
return NULL;
ListNode *pre = head, *cur,*tmp = new ListNode(0);
for(cur = head-& cur = cur-&next){
if(cur-&val == pre-&val){
pre-&next = cur-&
//不安全,待优化
1_2.return_nth_node_from_end_of_list
1.问题描述：
找到或者删除倒数第k个结点
2.解决策略
策略一：转成正数第m个
一轮遍历求链表长度
倒数第k个,即正数 m = n + 1 - k 个
遍历m个结点，返回第m个结点
策略二：快慢指针
快指针先走k步
接着快慢指针同时向前移动
直到链表遍历结束
返回慢指针指向的结点
3.调bug须知
边界测试用例：
单结点链表
传进来的头结点：
其实是第一个元素
最好自己新建个头结点
避免第一个结点特殊处理
删除结点如果是head结点：
A.只能想到加个if
B.返回head-&next
4.代码示例
/*************************************************************************
& File Name:
Solution.h
& Description:
（1）问题描述：
A.单向链表
B.找到或者删除倒数第k个结点
& Conclusion:
（1）策略一：转成正数第m个
A.一轮遍历求链表长度
B.倒数第k个,即正数 m = n + 1 - k 个
C.遍历m个结点，返回第m个结点
（2）策略二：快慢指针
A.快指针先走k步
B.接着快慢指针同时向前移动
C.直到链表遍历结束
D.返回慢指针指向的结点
（3）边界测试用例：
D.单结点链表
（4）传进来的头结点：
A.其实是第一个元素
B.最好自己新建个头结点
C.避免第一个结点特殊处理
（1）删除结点如果是head结点：
A.只能想到加个if
B.返回head-&next
rh_Jameson
& Created Time:
日 星期二 20时07分49秒
************************************************************************/
#ifndef _SOLUTION_H
#define _SOLUTION_H
#include&iostream&
#include&string&
#include&algorithm&
#include "LinkList.h"
class Solution {
//==================快慢指针实现====================//
void getNthNode(ListNode *head,int k){
if(head == NULL){
cout && "空链表" &&
if(k &= 0){
cout && "k值小于等于0，不合法" &&
ListNode *p_fast = new ListNode(0);
p_fast-&next =
for(int i = 0; i & i++){
//处理k & len的情况
if(p_fast == NULL){
cout && "k大于链表长度！" &&
p_fast = p_fast-&
ListNode *cur = new ListNode(0);
cur-&next =
while(p_fast != NULL){
p_fast = p_fast-&
cur = cur-&
cout && "倒数第k个值是" && cur-&val &&
//================转换成正数第m个===================//
void getNthNodeByM_th(ListNode *head,int k){
if(head == NULL){
cout && "空链表" &&
int len = 0;
ListNode *cur =
//求链表长度
while(cur != NULL){
cout && len && "\t";
cur = cur-&
if(k & len || k & 1){
cout && "k值不合法" &&
cout && head-&val &&
//遍历到第m个结点
int m_th = len + 1 -
for(int i = 1; i & m_ ++i){
cur = cur-&
cout && "倒数第k个的值是" && cur-&val &&
1_3.del_mid_node_from_list
1.问题描述:
只能访问某结点
且该结点要被移除
将该结点的下一个结点拷贝到该结点上
3.边界测试用例:
单结点链表
要删除结点是最后一个结点
4.代码示例：
/*************************************************************************
& File Name:
Solution.h
& Description:
（1）问题描述:
A.单向链表
B.只能访问某结点
C.且该结点要被移除
& Conclusion:
（1）策略:
A.将该结点的下一个结点拷贝到该结点上
B.注意边界
（2）边界测试用例:
B.单结点链表
C.要删除结点是最后一个结点
rh_Jameson
& Created Time:
日 星期二 21时58分22秒
************************************************************************/
#ifndef _SOLUTION_H
#define _SOLUTION_H
#include&iostream&
#include&string&
#include&algorithm&
#include"LinkList.h"
class Solution {
void removeMidNode(ListNode *midNode){
if(midNode == NULL || midNode-&next == NULL){
cout && "输入不合法" &&
*(midNode) = *(midNode-&next);
//midNode-&val = midNode-&next-&
//midNode-&next = midNode-&next-&
1_4.partition_list
1.问题描述：
链表分割成两部分
以给定值x为基准
小于x的结点在前
大于或等于x的结点在后
2.解决策略
策略一：另开链表
新建一链表
小于x，从原链表中删除
并将其插入新建链表中
结束一轮遍历后，连接两条链表
策略二：头插处理
比x小的结点，从链表中删除
再用头插法插入链表
3.关于策略二：
leetcode上不能使用头插法
书上也木有相似解法
原因：头插法顺序变化了
但题目没说要按原顺序啊～～
4.头结点（指第一个元素）改变的情况：
需改为指针的引用ListNode* &node
第一个元素往往要特殊对待
5.代码示例：
/*************************************************************************
& File Name:
Solution.h
& Description:
（1）问题描述：
A.链表分割成两部分
B.以给定值x为基准
C.小于x的结点在前
D. 大于或等于x的结点在后
& Conclusion:
（1）策略一：另开链表
A.新建一链表
B.小于x，从原链表中删除
C.并将其插入新建链表中
D. 结束一轮遍历后，连接两条链表
（2）策略二：头插处理
A.遍历链表
B.比x小的结点，从链表中删除
C.再用头插法插入链表
（3）关于策略二：
A.leetcode上不能使用头插法
B.书上也木有相似解法
C.原因：头插法顺序变化了
D.但题目没说要按原顺序啊～～
（4）头结点（指第一个元素）改变的情况：
A.需改为指针的引用ListNode* &node
B.第一个元素往往要特殊对待
rh_Jameson
& Created Time:
日 星期三 13时40分42秒
************************************************************************/
#ifndef _SOLUTION_H
#define _SOLUTION_H
#include&iostream&
#include&string&
#include&algorithm&
#include "LinkList.h"
class Solution {
//=====================另开一个链表======================//
ListNode *partitionByNewList(ListNode *head, int x) {
if(head == NULL){
return NULL;
if(head-&next == NULL){
//指针太多，晕死～～待优化ing
ListNode *cur = head,
*newList = new ListNode(x),
//新链表头结点
*new_cur = newL
//新链表游标
ListNode *pre = new ListNode(0),
*head_node = new ListNode(0),
//原链表头结点
pre-&next =
head_node-&next =
//遍历，小于x的从原链表中删除，加入新链表
while(cur != NULL){
if(cur-&val & x){
pre-&next = cur-&
if(cur == head_node-&next){
//待删元素是第一个元素特别处理
head_node-&next = cur-&
cur = cur-&
tmp-&next = NULL;
new_cur-&next =
new_cur = new_cur-&
cur = cur-&
//连接两个链表
new_cur-&next = head_node-&
return newList-&
//注意返回第一个元素而非头结点
//================================头插法实现============================//
void partition(ListNode * &head, int x){
//头结点变化情况下，须声明为ListNode* &head或ListNode **head
if(head == NULL){
cout && "空链表" &&
if(head-&next == NULL){
cout && "单节点链表" &&
ListNode *cur = head,
*pre = new ListNode(0),
*head_node = new ListNode(0);
pre-&next =
head_node-&next =
while(cur != NULL){
if(cur-&val & x && cur != head){
pre-&next = cur-&
cur-&next = head_node-&
head_node-&next =
cur = pre-&
cur = cur-&
head = head_node-&
1_5.add_two_num
1.问题描述：
有两个链表，每个结点含一个数位
两个链表代表两个整数
求两个整数之和
链表形式返回结果
数位分反向存放与正向存放两种情况
2.反向策略一：转为整型
声明两个加数变量
遍历两个链表
将结点的数位转到加数变量中
相加赋值到sum变量
链表形式逐位输出
关键公式：
a.v += p-&data * pow(10,i)
3.反向策略二：诸位添加
加入进位标志
将原有的两个链表对应结点值相加
所得之和插入新建链表中
进位标志为1时，注意所得之和需加1
4.coding遇到的问题
策略二需注意一下问题
其中一个链表已空，而另一链表还有元素
当两个链表为空时，进位标志仍为1
代码优化与复用，防止重复代码
新建结点相关：
如果可以，不用临时结点
减少相关指针，防止指针太多，影响思路
代码路径与优化：
存在多条代码路径时，需注意优化
尽可能找出路径之间的重合与关联
缩减/优化代码
正向存放待实现～～
5.代码示例：
/*************************************************************************
& File Name:
Solution.h
& Description:
（1）问题描述：
A.有两个链表，每个结点含一个数位
B.两个链表代表两个整数
C.求两个整数之和
D.链表形式返回结果
E.数位分反向存放与正向存放两种情况
& Conclusion:
（1）反向策略一：转为整型
A.声明两个加数变量
B.遍历两个链表
C.将结点的数位转到加数变量中
D.相加赋值到sum变量
E.链表形式逐位输出
F.关键公式：
a.v += p-&data * pow(10,i)
（2）反向策略二：诸位添加
A.加入进位标志
B.将原有的两个链表对应结点值相加
C.所得之和插入新建链表中
D.进位标志为1时，注意所得之和需加1
（3）策略二需注意一下问题
A.其中一个链表已空，而另一链表还有元素
B.当两个链表为空时，进位标志仍为1
C.代码优化与复用，防止重复代码
（4）新建结点相关：
A.如果可以，不用临时结点
B.减少相关指针，防止指针太多，影响思路
（5）代码路径与优化：
A.存在多条代码路径时，需注意优化
B.尽可能找出路径之间的重合与关联
C.缩减/优化代码
（6）正向存放待实现～～
rh_Jameson
& Created Time:
日 星期四 11时48分40秒
************************************************************************/
#ifndef _SOLUTION_H
#define _SOLUTION_H
#include&iostream&
#include&string&
#include&algorithm&
class Solution {
//=========================最终版：AC，省去多余指针=========================//
ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
ListNode *res_head = new ListNode(0), *cur = res_
int flag = 0, tmp_value = 0;
while(l1 != NULL || l2 != NULL || flag){
if(l1 != NULL){
tmp_value += l1-&
if(l2 != NULL){
tmp_value += l2-&
tmp_value +=
//判断是否有进位
if(tmp_value &= 10){
tmp_value %= 10;
//加入新结点
cur-&next = new ListNode(tmp_value);
cur = cur-&
tmp_value = 0;
return res_head-&
//=========================优化版2：AC，代码细节优化========================//
ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
//判两链表是否都为空
if(l1 == NULL && l2 == NULL){
return NULL;
ListNode *res_head = new ListNode(0), *cur = res_head, *
ListNode *cur_l1 = l1, *cur_l2 = l2;
int flag = 0, tmp_value = 0;
while(cur_l1 != NULL || cur_l2 != NULL || flag){
if(cur_l1 != NULL){
tmp_value += cur_l1-&
cur_l1 = cur_l1-&
if(cur_l2 != NULL){
tmp_value += cur_l2-&
cur_l2 = cur_l2-&
tmp_value +=
//判断是否有进位
if(tmp_value &= 10){
tmp_value %= 10;
//加入新结点
cur-&next = new ListNode(tmp_value);
cur = cur-&
tmp_value = 0;
return res_head-&
//====================优化版：AC，代码复用优化==============================//
ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
//判两链表是否都为空
if(l1 == NULL && l2 == NULL){
return NULL;
ListNode *res_head = new ListNode(0), *cur = res_head, *
ListNode *cur_l1 = l1, *cur_l2 = l2;
int flag = 0;
while(cur_l1 != NULL || cur_l2 != NULL){
//l1链表空，l2还有结点的情况
if(cur_l1 == NULL){
tmp_value = cur_l2-&val +
cur_l2 = cur_l2-&
//l2链表空，l1还有结点的情况
else if(cur_l2 == NULL){
tmp_value = cur_l1-&val +
cur_l1 = cur_l1-&
//l1,l2均有链表的情况
tmp_value = cur_l1-&val + cur_l2-&val +
cur_l1 = cur_l1-&
cur_l2 = cur_l2-&
//判断是否有进位
if(tmp_value &= 10){
tmp_value %= 10;
//加入新结点
tmp = new ListNode(tmp_value);
tmp-&next = NULL;
cur-&next =
cur = cur-&
if(flag == 1){
tmp = new ListNode(1);
tmp-&next = NULL;
cur-&next =
return res_head-&
//====================原始版：AC，但代码冗长，重复太多======================//
void addTwoNumbers(ListNode *l1, ListNode *l2) {
ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
if(l1 == NULL && l2 == NULL){
return NULL;
ListNode *res_head = new ListNode(0), *cur = res_head, *tmp, *new_
ListNode *cur_l1 = l1, *cur_l2 = l2;
int flag = 0;
while(cur_l1 != NULL || cur_l2 != NULL){
//l1链表空，l2还有结点的情况
if(cur_l1 == NULL){
tmp = cur_l2;
while(flag == 1){
cur_l2-&val +=
if(cur_l2-&val &= 10){
cur_l2-&val %= 10;
if(cur_l2-&next != NULL){
cur_l2 = cur_l2-&
new_node = new ListNode(1);
cur_l2-&next = new_
cur-&next =
//l2链表空，l1还有结点的情况
if(cur_l2 == NULL){
tmp = cur_l1;
while(flag == 1){
cur_l1-&val +=
if(cur_l1-&val &= 10){
cur_l1-&val %= 10;
if(cur_l1-&next != NULL){
cur_l1 = cur_l1-&
new_node = new ListNode(1);
cur_l1-&next = new_
cur-&next =
if(flag == false){
tmp_value = cur_l1-&val + cur_l2-&
tmp_value = cur_l1-&val + cur_l2-&val +
if(tmp_value &= 10){
tmp_value %= 10;
tmp = new ListNode(tmp_value);
tmp-&next = NULL;
cur-&next =
cur = cur-&
cur_l1 = cur_l1-&
cur_l2 = cur_l2-&
if(flag == 1){
new_node = new ListNode(1);
new_node-&next = NULL;
cur-&next = new_
return res_head-&
1_6.link_list_cycle
1.问题描述：
判断是否是有环链表
返回环路开头结点
2.链表相关注意：
做链表题目时，一定要理清思路后再实现
注意边界用例特殊情况
最好能画图在纸上确保木有问题了再转成代码
3.策略 & 思路：快慢指针
设定一快一慢指针,p_fast & p_slow
p_slow走一步，p_fast走两步
设p_slow走k步进入环，到达环的入口接点
此时，p_slow = k, p_fast = 2k
快慢相距 （p_fast - p_slow）k 步
设环总长度为L，则快慢反向相距L - k步
快慢指针每移动一位，反向相距长度就减一
移动L - k次后，快慢相遇
此时慢指针在环内走了L - k步
即慢指针距离入口结点：
L - （L - k） = k
快慢相遇后，慢指针指回头结点
快慢继续向前推进
当快慢指针的指向值相等时，即是环路开头结点
4.代码示例：
/*************************************************************************
& File Name:
Solution.h
& Description:
(1)问题描述：
B.判断是否是有环链表
C.返回环路开头结点
& Conclusion:
(1)策略 & 思路：快慢指针
A.设定一快一慢指针,p_fast & p_slow
B.p_slow走一步，p_fast走两步
C.设p_slow走k步进入环，到达环的入口接点
a.此时，p_slow = k, p_fast = 2k
b.快慢相距 （p_fast - p_slow）k 步
D. 设环总长度为L，则快慢反向相距L - k步
E.快慢指针每移动一位，反向相距长度就减一
a.移动L - k次后，快慢相遇
b.此时慢指针在环内走了L - k步
F.即慢指针距离入口结点：
L - （L - k） = k
G.快慢相遇后，慢指针指回头结点
H.快慢继续向前推进
I.当快慢指针的指向值相等时，即是环路开头结点
(2)链表相关注意：
A.做链表题目时，一定要理清思路后再实现
B.注意边界用例特殊情况
C.最好能画图在纸上确保木有问题了再转成代码
(1)问题描述：
rh_Jameson
& Created Time:
日 星期五 17时41分07秒
************************************************************************/
#ifndef _SOLUTION_H
#define _SOLUTION_H
#include&iostream&
#include&string&
#include&algorithm&
class Solution {
//===================快慢指针返回环入口结点：自增头结点版本====================//
ListNode *detectCycle(ListNode *head) {
//定义头结点，快慢指针
ListNode *head_node = new ListNode(0);
//p_slow = NULL OK?
head_node-&next =
ListNode *p_slow = head_node, *p_fast = head_
while(p_slow != p_fast || p_slow == head_node){
//如p_fast已指向链表尾部，返回NULL
if(p_fast-&next == NULL || p_fast-&next-&next == NULL){
return NULL;
//快慢向前推进
p_slow = p_slow-&
p_fast = p_fast-&next-&
//慢指针重置
p_slow = head_
//快慢指针重新向前推进，直至相遇
while(p_slow != p_fast){
p_slow = p_slow-&
p_fast = p_fast-&
//============快慢指针返回环入口结点：无头结点优化版本（非本人代码）=============//
ListNode *detectCycle(ListNode *head) {
ListNode *fast =
ListNode *slow =
ListNode *detect =
while(fast != NULL && fast-&next != NULL){
slow = slow-&
fast = fast-&next-&
if(slow == detect)
if(slow == fast) detect = detect-&
return NULL;
//========================判断链表是否是有环链表========================//
bool hasCycle(ListNode *head) {
ListNode *head_node = new ListNode(0);
//p_slow = NULL OK?
head_node-&next =
ListNode *p_slow = head_node, *p_fast = head_
while(p_slow != p_fast || p_slow == head_node){
if(!p_fast-&next || !p_fast-&next-&next){
p_slow = p_slow-&
p_fast = p_fast-&next-&
1_7.isPalindrome
1.问题描述：
检测链表是否为回文
2.策略一：数组保存原链表
同时将结点存入数组
遍历新链表
同时与数组相应位置比较
相等移入下一位置
不等返回false
3.策略二：快慢指针实现
快慢指针进行一轮遍历
慢指针将链表分段
对前半段进行反转
遍历判断前后两段元素是否相等
4.策略二优化：
慢指针边移动时，边反转元素
代码搅在一起也不是一件好事
代码出错率增加
5.代码示例：
/*************************************************************************
& File Name:
Solution.h
& Description:
（1）问题描述：
A.检测链表是否为回文
& Conclusion:
（1）策略一：数组保存原链表
A.逆置链表
B.同时将结点存入数组
C.遍历新链表
D.同时与数组相应位置比较
E.相等移入下一位置
F.不等返回false
（2）策略二：快慢指针实现
A.快慢指针进行一轮遍历
B.慢指针将链表分段
C.对前半段进行反转
D. 遍历判断前后两段元素是否相等
（3）策略二优化：
A.慢指针边移动时，边反转元素
B.代码搅在一起也不是一件好事
C.代码出错率增加
rh_Jameson
& Created Time:
日 星期四 17时52分27秒
************************************************************************/
#ifndef _SOLUTION_H
#define _SOLUTION_H
#include&iostream&
#include&string&
#include&algorithm&
#include&vector&
#include "LinkList.h"
class Solution {
//==========================优化（有潜在边界问题）：不使用使用额外数组判断回文======================//
void isPalindrome(ListNode *head){
if(head == NULL){
cout && "NULL LinkList!" &&
if(head-&next == NULL){
cout && "single node LinkList!" &&
if(head-&next-&next == NULL){
if(head-&val != head-&next-&val){
cout && "it is not a Palindrome" &&
cout && "it is a Palindrome" &&
//快慢指针遍历链表，同时反转p_slow前面的结点
ListNode *p_slow = head, *p_fast = head-&
ListNode *pre = NULL, *cur = head, *p_
while(p_fast != NULL){
p_slow = p_slow-&
p_fast = p_fast-&next-&
p_next = cur-&
cur-&next =
if(p_fast-&next == NULL){
p_next = cur-&
cur-&next =
//链表长度为奇数的话，cur要向前移动一位
if(p_fast == NULL){
cur = cur-&
//判断两段链表相应结点值是否相等
while(pre != NULL){
if(pre-&val != cur-&val){
cout && "it is not a Palindrome" &&
pre = pre-&
cur = cur-&
cout && "it is a Palindrome" &&
//==========================不使用额外数组判断回文======================//
void isPalindromeByPtr(ListNode *head){
if(head == NULL){
cout && "NULL LinkList!" &&
if(head-&next == NULL){
cout && "single node LinkList!" &&
//快慢指针遍历链表
ListNode *p_slow = head, *p_fast = head-&
while(p_fast-&next != NULL && p_fast-&next-&next != NULL){
//-&next-&next 这里发生段错误，需加入前半段才行
p_slow = p_slow-&
p_fast = p_fast-&next-&
//反转p_slow前半段结点
ListNode *pre = NULL, *cur = head, *p_
while(pre != p_slow){
p_next = cur-&
cur-&next =
//链表长度为奇数的话，cur要向前移动一位
if(p_fast-&next != NULL){
cur = cur-&
//判断两段链表相应结点值是否相等
while(pre != NULL){
if(pre-&val != cur-&val){
cout && "it is not a Palindrome" &&
pre = pre-&
cur = cur-&
cout && "it is a Palindrome" &&
//==========================使用额外数组存放原顺序======================//
void isPalindromeByArray(ListNode *head){
if(head == NULL){
cout && "空链表" &&
if(head-&next == NULL){
cout && "单结点链表：" && head-&val &&
vector&int& vec_
ListNode *pre = NULL, *cur = head, *p_
while(cur != NULL){
vec_pal.push_back(cur-&val);
p_next = cur-&
cur-&next =
for(vector&int&::iterator i = vec_pal.begin(); i & vec_pal.end();++i){
if(*i != cur-&val){
cout && "不是回文" &&
cur = cur-&
cout && "是回文链表！" &&
1_8.removeDuplicatesFromSortedList
代码示例：
/*************************************************************************
& File Name:
Solution.h
& Description:
（1）问题描述
A.已排序链表
B.移除重复节点
& Conclusion:
（1）策略一：
A.链表排序
B.通过快慢指针消除重复元素
（2）策略二：
A.哈希表储存元素
B.遍历链表
C.遇到重复元素，从链表中删去.
rh_Jameson
& Created Time:
日 星期二 11时36分52秒
************************************************************************/
#ifndef _SOLUTION_H
#define _SOLUTION_H
#include&iostream&
#include&string&
#include&algorithm&
#include&map&
#include&cstdlib&
#include&ctime&
#include "LinkList.h"
class Solution {
//=================哈希实现：空间O（M）,时间O（N）====================//
void removeDuplicatesFromLinklistByHash(ListNode *head){
if(head == NULL){
cout && "空链表" &&
//哈希实现
map&int, int& unique_
ListNode *p = head, *tmp = new ListNode(0);
ListNode *q = head-&
unique_map[p-&val] = p-&
for(q = head-& q != NULL; q = q-&next){
if(unique_map.count(q-&val)){
p-&next = q-&
unique_map[q-&val] = q-&
//===================while形式====================//
while(q != NULL){
if(unique_map.count(q-&val)){
p-&next = q-&
unique_map[q-&val] = q-&
//=================================两个指针实现版=======================================//
ListNode *deleteDuplicates(ListNode *head) {
//头结点是第一个结点
if(head == NULL){
return NULL;
ListNode *pre = head, *cur,*tmp = new ListNode(0);
for(cur = head-& cur = cur-&next){
if(cur-&val == pre-&val){
pre-&next = cur-&
//不安全,待优化
大学的时候不好好学习，老师在讲台上讲课，自己在以为老师看不到的座位看小说，现在用到了老师讲的知识，只能自己看书查资料进行再回炉学习，真心对不住老师，对不住父母，对不住自己的青春啊！ 有些路，就是需要你自己走，有些知识就是需要你掌握，不论早几年还是现在还是几年后。。。是你的终...
本文内容取自于小甲鱼的数据结构与算法。http://www.jianshu.com/p/230e6fde9c75 1. 线性表 线性表（List）：由零个或多个数据元素组成的有限序列。 这里需要强调几个关键的地方： 首先它是一个序列，也就是说元素之间是有个先来后到的。若元素...
前言 本文是题主准备面试时记录下的笔记整理而来，稍显粗陋，还请各位撸友勿喷哈！ Topic 目录数组字符串链表二叉树排序 目标熟练使用常用数据结构的基本操作加深对常用算法与技巧的理解面试 参考《程序员面试金典》《剑指offer》Leetcode《结构之法 --July》 字...
B树的定义 一棵m阶的B树满足下列条件： 树中每个结点至多有m个孩子。 除根结点和叶子结点外，其它每个结点至少有m/2个孩子。 根结点至少有2个孩子（如果B树只有一个结点除外）。 所有叶结点在同一层，B树的叶结点可以看成一种外部节点，不包含任何信息。 有k个关键字(关键字按...
转载请注明出处：http://www.jianshu.com/p/c65d9d753c31 在上一篇博客《数据结构与算法（二），线性表》中介绍了线性表的创建、插入、删除等基本操作，这一篇将总结一下链表中最常考的面试题。 目录： 1、从尾到头打印单链表 2、在O(1)时间删除...
早上六点多醒了，但是一直觉得冷不想起床，八点多才起床。体重和昨天早上一样。毕竟昨天中午吃了米饭和菜。起床后看看面发的很好。今天早上还是炸油条，做胡辣汤。面上上周的两倍，胡辣汤没有上周的辣。不过还是一样好喝。炸油条时有个小插曲，陈从油锅里把熟油条夹出来时因为长度不一有一根油条...
时尚就是一个轮回，活着活着你有没有发现小学穿的校裤现在火了，虽然还抵不过路上小姑娘撞裤程度100%的网袜+破洞牛仔裤的搭配，但是这阵风也是越吹越烈。 十年前，天空晴朗，绿草如茵，听着《雏鹰起飞》的“伴奏”，迎着春光，我们脖子上的红领巾闪闪发光，比他更闪亮的是我们身上这套低调...
你像转世的仙子 美丽如斯 装点无数凡尘 而我只是 浮世海的过客 当生命的舟帆相会 我荒芜枯寂的地方 就化成片片桃源 可那交会仅仅一瞬 然后相望着离开 把那当做梦幻 甚至仅仅偶然 转身后就不见 你最好忘掉 我最好离开 连回首都不要 我怕直到漂流到忘川 你仍是我对岸的梦幻
崔武子见棠姜而美之，遂取（娶）之。庄公通焉。崔子弑之。 《左传》襄公二十五年中，详细记载了齐庄公因为通奸大臣崔杼夫人而被大臣杀死的全过程，当然，此次我们的重点是庄公死后的引起的故事，庄公我们之后再谈，这又是一起“甚美必有甚恶”的典例。 庄公之死，引出了历史上非常有名的一位大...
一、提交人信息 姓名：沈玉含 所属小组：Geekest 二、学习信息 开始学习时间：日 12:00 结束学习时间：日 12:30 学习感受书写开始时间：日 14:15 学习感受书写完成时间：日 ...}