程序员面试之算法备忘录(三) | 链表

前言


本文是题主准备面试时记录下的笔记整理而来,稍显粗陋,还请各位撸友勿喷哈!

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


最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 206,126评论 6 481
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 88,254评论 2 382
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 152,445评论 0 341
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 55,185评论 1 278
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 64,178评论 5 371
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,970评论 1 284
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,276评论 3 399
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,927评论 0 259
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 43,400评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,883评论 2 323
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,997评论 1 333
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,646评论 4 322
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,213评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,204评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,423评论 1 260
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,423评论 2 352
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,722评论 2 345

推荐阅读更多精彩内容