程序员面试之算法备忘录（三） | 链表
2016-06-02 本文已影响632人
rh_Jameson
前言
本文是题主准备面试时记录下的笔记整理而来，稍显粗陋，还请各位撸友勿喷哈！
Topic
-
目标
- 熟练使用常用数据结构的基本操作
- 加深对常用算法与技巧的理解
- 面试
-
参考
- 《程序员面试金典》
- 《剑指offer》
- Leetcode
- 《结构之法 --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.遇到重复元素，从链表中删去.
> Author: rh_Jameson
> Created Time: 2014年12月16日 星期二 11时36分52秒
************************************************************************/
#ifndef _SOLUTION_H
#define _SOLUTION_H
#include<iostream>
#include<string>
#include<algorithm>
#include<map>
#include<cstdlib>
#include<ctime>
#include "LinkList.h"
using namespace std;
class Solution {
public:
//=================哈希实现：空间O（M）,时间O（N）====================//
void removeDuplicatesFromLinklistByHash(ListNode *head){
//判空
if(head == NULL){
cout << "空链表" << endl;
}
//哈希实现
map<int, int> unique_map;
ListNode *p = head, *tmp = new ListNode(0);
ListNode *q = head->next;
unique_map[p->val] = p->val;
for(q = head->next; q != NULL; q = q->next){
if(unique_map.count(q->val)){
p->next = q->next;
tmp = q;
q = p;
delete tmp;
}
else{
unique_map[q->val] = q->val;
p = p->next;
}
}
//===================while形式====================//
/*
while(q != NULL){
if(unique_map.count(q->val)){
p->next = q->next;
tmp = q;
q = q->next;
delete tmp;
}
else{
unique_map[q->val] = q->val;
p = p->next;
q = q->next;
}
}
*/
}
//=================================两个指针实现版=======================================//
ListNode *deleteDuplicates(ListNode *head) { //头结点是第一个结点
if(head == NULL){
return NULL;
}
ListNode *pre = head, *cur,*tmp = new ListNode(0);
for(cur = head->next; cur; cur = cur->next){
if(cur->val == pre->val){
pre->next = cur->next;
delete cur; //不安全,待优化
}
else{
pre = cur;
}
}
return head;
}
};
#endif
1_2.return_nth_node_from_end_of_list
1.问题描述：
- 单向链表
- 找到或者删除倒数第k个结点
2.解决策略
-
策略一：转成正数第m个
- 一轮遍历求链表长度
- 倒数第k个,即正数 m = n + 1 - k 个
- 遍历m个结点，返回第m个结点
-
策略二：快慢指针
- 快指针先走k步
- 接着快慢指针同时向前移动
- 直到链表遍历结束
- 返回慢指针指向的结点
3.调bug须知
-
边界测试用例：
- 空链表
- k > n
- k < 0
- 单结点链表
-
传进来的头结点：
- 其实是第一个元素
- 最好自己新建个头结点
- 避免第一个结点特殊处理
-
删除结点如果是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）边界测试用例：
A.空链表
B.k > n
C.k < 0
D.单结点链表
（4）传进来的头结点：
A.其实是第一个元素
B.最好自己新建个头结点
C.避免第一个结点特殊处理
（1）删除结点如果是head结点：
A.只能想到加个if
B.返回head->next
> Author: rh_Jameson
> Created Time: 2014年12月16日 星期二 20时07分49秒
************************************************************************/
#ifndef _SOLUTION_H
#define _SOLUTION_H
#include<iostream>
#include<string>
#include<algorithm>
#include "LinkList.h"
using namespace std;
class Solution {
public:
//==================快慢指针实现====================//
void getNthNode(ListNode *head,int k){
if(head == NULL){
cout << "空链表" << endl;
return;
}
if(k <= 0){
cout << "k值小于等于0，不合法" << endl;
return;
}
ListNode *p_fast = new ListNode(0);
p_fast->next = head;
//
for(int i = 0; i < k; i++){
//处理k > len的情况
if(p_fast == NULL){
cout << "k大于链表长度！" << endl;
return;
}
p_fast = p_fast->next;
}
ListNode *cur = new ListNode(0);
cur->next = head;
while(p_fast != NULL){
p_fast = p_fast->next;
cur = cur->next;
}
cout << "倒数第k个值是" << cur->val << endl;
}
//================转换成正数第m个===================//
void getNthNodeByM_th(ListNode *head,int k){
if(head == NULL){
cout << "空链表" << endl;
return;
}
int len = 0;
ListNode *cur = head;
//求链表长度
while(cur != NULL){
++len;
cout << len << "\t";
cur = cur->next;
}
cout << endl;
if(k > len || k < 1){
cout << "k值不合法" << endl;
return;
}
cout << endl;
cout << head->val << endl;
cur = head; //重置
//遍历到第m个结点
int m_th = len + 1 - k;
for(int i = 1; i < m_th; ++i){
cur = cur->next;
}
cout << "倒数第k个的值是" << cur->val << endl;
}
};
#endif
1_3.del_mid_node_from_list
1.问题描述:
- 单向链表
- 只能访问某结点
- 且该结点要被移除
2.策略:
- 将该结点的下一个结点拷贝到该结点上
- 注意边界
3.边界测试用例:
- 空链表
- 单结点链表
- 要删除结点是最后一个结点
4.代码示例：
/*************************************************************************
> File Name: Solution.h
> Description:
（1）问题描述:
A.单向链表
B.只能访问某结点
C.且该结点要被移除
> Conclusion:
（1）策略:
A.将该结点的下一个结点拷贝到该结点上
B.注意边界
（2）边界测试用例:
A.空链表
B.单结点链表
C.要删除结点是最后一个结点
> Author: rh_Jameson
> Created Time: 2014年12月16日 星期二 21时58分22秒
************************************************************************/
#ifndef _SOLUTION_H
#define _SOLUTION_H
#include<iostream>
#include<string>
#include<algorithm>
#include"LinkList.h"
using namespace std;
class Solution {
public:
void removeMidNode(ListNode *midNode){
if(midNode == NULL || midNode->next == NULL){
cout << "输入不合法" << endl;
}
*(midNode) = *(midNode->next);
//midNode->val = midNode->next->val;
//midNode->next = midNode->next->next;
}
};
#endif
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.第一个元素往往要特殊对待
> Author: rh_Jameson
> Created Time: 2014年12月17日 星期三 13时40分42秒
************************************************************************/
#ifndef _SOLUTION_H
#define _SOLUTION_H
#include<iostream>
#include<string>
#include<algorithm>
#include "LinkList.h"
using namespace std;
class Solution {
public:
//=====================另开一个链表======================//
ListNode *partitionByNewList(ListNode *head, int x) {
if(head == NULL){
return NULL;
}
if(head->next == NULL){
return head;
}
//指针太多，晕死～～待优化ing
ListNode *cur = head,
*newList = new ListNode(x), //新链表头结点
*new_cur = newList; //新链表游标
ListNode *pre = new ListNode(0),
*head_node = new ListNode(0), //原链表头结点
*tmp;
pre->next = cur;
head_node->next = head;
//遍历，小于x的从原链表中删除，加入新链表
while(cur != NULL){
if(cur->val < x){
tmp = cur;
pre->next = cur->next;
if(cur == head_node->next){ //待删元素是第一个元素特别处理
head_node->next = cur->next;
}
cur = cur->next;
tmp->next = NULL;
new_cur->next = tmp;
new_cur = new_cur->next;
}
else{
pre = cur;
cur = cur->next;
}
}
//连接两个链表
new_cur->next = head_node->next;
return newList->next; //注意返回第一个元素而非头结点
}
//================================头插法实现============================//
void partition(ListNode * &head, int x){ //头结点变化情况下，须声明为ListNode* &head或ListNode **head
if(head == NULL){
cout << "空链表" << endl;
return;
}
if(head->next == NULL){
cout << "单节点链表" << endl;
return;
}
ListNode *cur = head,
*pre = new ListNode(0),
*head_node = new ListNode(0);
pre->next = head;
head_node->next = head;
while(cur != NULL){
if(cur->val < x && cur != head){
pre->next = cur->next;
cur->next = head_node->next;
head_node->next = cur;
cur = pre->next;
}
else{
pre = cur;
cur = cur->next;
}
}
head = head_node->next;
}
};
#endif
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）正向存放待实现～～
> Author: rh_Jameson
> Created Time: 2014年12月18日 星期四 11时48分40秒
************************************************************************/
#ifndef _SOLUTION_H
#define _SOLUTION_H
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
class Solution {
public:
//=========================最终版：AC，省去多余指针=========================//
ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
ListNode *res_head = new ListNode(0), *cur = res_head;
int flag = 0, tmp_value = 0;
while(l1 != NULL || l2 != NULL || flag){
//计算和
if(l1 != NULL){
tmp_value += l1->val;
l1 = l1->next;
}
if(l2 != NULL){
tmp_value += l2->val;
l2 = l2->next;
}
tmp_value += flag;
//判断是否有进位
if(tmp_value >= 10){
flag = 1;
tmp_value %= 10;
}
else{
flag = 0;
}
//加入新结点
cur->next = new ListNode(tmp_value);
cur = cur->next;
tmp_value = 0;
}
return res_head->next;
}
//=========================优化版2：AC，代码细节优化========================//
ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
//判两链表是否都为空
if(l1 == NULL && l2 == NULL){
return NULL;
}
ListNode *res_head = new ListNode(0), *cur = res_head, *tmp;
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->val;
cur_l1 = cur_l1->next;
}
if(cur_l2 != NULL){
tmp_value += cur_l2->val;
cur_l2 = cur_l2->next;
}
tmp_value += flag;
//判断是否有进位
if(tmp_value >= 10){
flag = 1;
tmp_value %= 10;
}
else{
flag = 0;
}
//加入新结点
cur->next = new ListNode(tmp_value);
cur = cur->next;
tmp_value = 0;
}
return res_head->next;
}
//====================优化版：AC，代码复用优化==============================//
ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
//判两链表是否都为空
if(l1 == NULL && l2 == NULL){
return NULL;
}
ListNode *res_head = new ListNode(0), *cur = res_head, *tmp;
ListNode *cur_l1 = l1, *cur_l2 = l2;
int flag = 0;
int tmp_value;
while(cur_l1 != NULL || cur_l2 != NULL){
//l1链表空，l2还有结点的情况
if(cur_l1 == NULL){
tmp_value = cur_l2->val + flag;
cur_l2 = cur_l2->next;
}
//l2链表空，l1还有结点的情况
else if(cur_l2 == NULL){
tmp_value = cur_l1->val + flag;
cur_l1 = cur_l1->next;
}
//l1,l2均有链表的情况
else{
tmp_value = cur_l1->val + cur_l2->val + flag;
cur_l1 = cur_l1->next;
cur_l2 = cur_l2->next;
}
//判断是否有进位
if(tmp_value >= 10){
flag = 1;
tmp_value %= 10;
}
else{
flag = 0;
}
//加入新结点
tmp = new ListNode(tmp_value);
tmp->next = NULL;
cur->next = tmp;
cur = cur->next;
}
if(flag == 1){
tmp = new ListNode(1);
tmp->next = NULL;
cur->next = tmp;
flag = 0;
}
return res_head->next;
}
//====================原始版：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_node;
ListNode *cur_l1 = l1, *cur_l2 = l2;
int flag = 0;
int tmp_value;
while(cur_l1 != NULL || cur_l2 != NULL){
//l1链表空，l2还有结点的情况
if(cur_l1 == NULL){
tmp = cur_l2;
while(flag == 1){
cur_l2->val += flag;
if(cur_l2->val >= 10){
cur_l2->val %= 10;
if(cur_l2->next != NULL){
cur_l2 = cur_l2->next;
}
else{
new_node = new ListNode(1);
cur_l2->next = new_node;
flag = 0;
}
}
else{
flag = 0;
}
}
cur->next = tmp;
break;
}
//l2链表空，l1还有结点的情况
if(cur_l2 == NULL){
tmp = cur_l1;
while(flag == 1){
cur_l1->val += flag;
if(cur_l1->val >= 10){
cur_l1->val %= 10;
if(cur_l1->next != NULL){
cur_l1 = cur_l1->next;
}
else{
new_node = new ListNode(1);
cur_l1->next = new_node;
flag = 0;
}
}
else{
flag = 0;
}
}
cur->next = tmp;
break;
}
if(flag == false){
tmp_value = cur_l1->val + cur_l2->val;
}
else{
tmp_value = cur_l1->val + cur_l2->val + flag;
flag = 0;
}
if(tmp_value >= 10){
flag = 1;
tmp_value %= 10;
}
tmp = new ListNode(tmp_value);
tmp->next = NULL;
cur->next = tmp;
cur = cur->next;
cur_l1 = cur_l1->next;
cur_l2 = cur_l2->next;
}
if(flag == 1){
new_node = new ListNode(1);
new_node->next = NULL;
cur->next = new_node;
flag = 0;
}
return res_head->next;
}
};
#endif
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)问题描述：
A.链表
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)问题描述：
A.
B.
C.
D.
> Author: rh_Jameson
> Created Time: 2014年12月19日 星期五 17时41分07秒
************************************************************************/
#ifndef _SOLUTION_H
#define _SOLUTION_H
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
class Solution {
public:
//===================快慢指针返回环入口结点：自增头结点版本====================//
ListNode *detectCycle(ListNode *head) {
//定义头结点，快慢指针
ListNode *head_node = new ListNode(0); //p_slow = NULL OK?
head_node->next = head;
ListNode *p_slow = head_node, *p_fast = head_node;
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->next;
p_fast = p_fast->next->next;
}
//慢指针重置
p_slow = head_node;
//快慢指针重新向前推进，直至相遇
while(p_slow != p_fast){
p_slow = p_slow->next;
p_fast = p_fast->next;
}
return p_slow;
}
//============快慢指针返回环入口结点：无头结点优化版本（非本人代码）=============//
ListNode *detectCycle(ListNode *head) {
ListNode *fast = head;
ListNode *slow = head;
ListNode *detect = head;
while(fast != NULL && fast->next != NULL){
slow = slow->next;
fast = fast->next->next;
if(slow == detect) return detect;
if(slow == fast) detect = detect->next;
}
return NULL;
}
//========================判断链表是否是有环链表========================//
bool hasCycle(ListNode *head) {
ListNode *head_node = new ListNode(0); //p_slow = NULL OK?
head_node->next = head;
ListNode *p_slow = head_node, *p_fast = head_node;
while(p_slow != p_fast || p_slow == head_node){
if(!p_fast->next || !p_fast->next->next){
return false;
}
p_slow = p_slow->next;
p_fast = p_fast->next->next;
}
return true;
}
};
#endif
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.代码出错率增加
> Author: rh_Jameson
> Created Time: 2014年12月18日 星期四 17时52分27秒
************************************************************************/
#ifndef _SOLUTION_H
#define _SOLUTION_H
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include "LinkList.h"
using namespace std;
class Solution {
public:
//==========================优化（有潜在边界问题）：不使用使用额外数组判断回文======================//
void isPalindrome(ListNode *head){
if(head == NULL){
cout << "NULL LinkList!" << endl;
return;
}
if(head->next == NULL){
cout << "single node LinkList!" << endl;
return;
}
if(head->next->next == NULL){
if(head->val != head->next->val){
cout << "it is not a Palindrome" << endl;
return;
}
else{
cout << "it is a Palindrome" << endl;
return;
}
}
//快慢指针遍历链表，同时反转p_slow前面的结点
ListNode *p_slow = head, *p_fast = head->next;
ListNode *pre = NULL, *cur = head, *p_next;
while(p_fast != NULL){
p_slow = p_slow->next;
p_fast = p_fast->next->next;
p_next = cur->next;
cur->next = pre;
pre = cur;
cur = p_next;
if(p_fast->next == NULL){
p_next = cur->next;
cur->next = pre;
pre = cur;
cur = p_next;
break;
}
}
//链表长度为奇数的话，cur要向前移动一位
if(p_fast == NULL){
cur = cur->next;
}
//判断两段链表相应结点值是否相等
while(pre != NULL){
if(pre->val != cur->val){
cout << "it is not a Palindrome" << endl;
return;
}
pre = pre->next;
cur = cur->next;
}
cout << "it is a Palindrome" << endl;
}
//==========================不使用额外数组判断回文======================//
void isPalindromeByPtr(ListNode *head){
if(head == NULL){
cout << "NULL LinkList!" << endl;
return;
}
if(head->next == NULL){
cout << "single node LinkList!" << endl;
return;
}
//快慢指针遍历链表
ListNode *p_slow = head, *p_fast = head->next;
while(p_fast->next != NULL && p_fast->next->next != NULL){ //->next->next 这里发生段错误，需加入前半段才行
p_slow = p_slow->next;
p_fast = p_fast->next->next;
}
//反转p_slow前半段结点
ListNode *pre = NULL, *cur = head, *p_next;
while(pre != p_slow){
p_next = cur->next;
cur->next = pre;
pre = cur;
cur = p_next;
}
//链表长度为奇数的话，cur要向前移动一位
if(p_fast->next != NULL){
cur = cur->next;
}
//判断两段链表相应结点值是否相等
while(pre != NULL){
if(pre->val != cur->val){
cout << "it is not a Palindrome" << endl;
return;
}
pre = pre->next;
cur = cur->next;
}
cout << "it is a Palindrome" << endl;
}
//==========================使用额外数组存放原顺序======================//
void isPalindromeByArray(ListNode *head){
if(head == NULL){
cout << "空链表" << endl;
return;
}
if(head->next == NULL){
cout << "单结点链表：" << head->val << endl;
return;
}
vector<int> vec_pal;
ListNode *pre = NULL, *cur = head, *p_next;
while(cur != NULL){
vec_pal.push_back(cur->val);
p_next = cur->next;
cur->next = pre;
pre = cur;
cur = p_next;
}
head = pre;
cur = pre;
for(vector<int>::iterator i = vec_pal.begin(); i < vec_pal.end();++i){
if(*i != cur->val){
cout << "不是回文" << endl;
return;
}
cur = cur->next;
}
cout << "是回文链表！" << endl;
}
};
#endif
1_8.removeDuplicatesFromSortedList
代码示例：
/*************************************************************************
> File Name: Solution.h
> Description:
（1）问题描述
A.已排序链表
B.移除重复节点
> Conclusion:
（1）策略一：
A.链表排序
B.通过快慢指针消除重复元素
（2）策略二：
A.哈希表储存元素
B.遍历链表
C.遇到重复元素，从链表中删去.
> Author: rh_Jameson
> Created Time: 2014年12月16日 星期二 11时36分52秒
************************************************************************/
#ifndef _SOLUTION_H
#define _SOLUTION_H
#include<iostream>
#include<string>
#include<algorithm>
#include<map>
#include<cstdlib>
#include<ctime>
#include "LinkList.h"
using namespace std;
class Solution {
public:
//=================哈希实现：空间O（M）,时间O（N）====================//
void removeDuplicatesFromLinklistByHash(ListNode *head){
//判空
if(head == NULL){
cout << "空链表" << endl;
}
//哈希实现
map<int, int> unique_map;
ListNode *p = head, *tmp = new ListNode(0);
ListNode *q = head->next;
unique_map[p->val] = p->val;
for(q = head->next; q != NULL; q = q->next){
if(unique_map.count(q->val)){
p->next = q->next;
tmp = q;
q = p;
delete tmp;
}
else{
unique_map[q->val] = q->val;
p = p->next;
}
}
//===================while形式====================//
/*
while(q != NULL){
if(unique_map.count(q->val)){
p->next = q->next;
tmp = q;
q = q->next;
delete tmp;
}
else{
unique_map[q->val] = q->val;
p = p->next;
q = q->next;
}
}
*/
}
//=================================两个指针实现版=======================================//
ListNode *deleteDuplicates(ListNode *head) { //头结点是第一个结点
if(head == NULL){
return NULL;
}
ListNode *pre = head, *cur,*tmp = new ListNode(0);
for(cur = head->next; cur; cur = cur->next){
if(cur->val == pre->val){
pre->next = cur->next;
delete cur; //不安全,待优化
}
else{
pre = cur;
}
}
return head;
}
};
#endif
