【手绘漫画】面试必考之手撕双链表(解题模板和深度剖析),(LeetCode 707)

在这里插入图片描述

图解算法与数据结构

1、前言

今天开始链表,这一讲是单链表,下一讲是双链表。

下面一起来看看吧!!!
在这里插入图片描述
在这里插入图片描述

2、代码

模板:

//C++双向链表模板
class MyLinkedList{
private:
    struct ListNode{
        int val;
        ListNode *next,*prev;
        ListNode(int x):val(x),next(nullptr),prev(nullptr){}
    };
private:
    //头节点尾节点都为空,表示为空链表
    ListNode *head,*tail;
    int size=0;
public:
    MyLinkedList():size(0),head(nullptr),tail(nullptr){}

    int get(int index){
        int i=0;
        ListNode *p=head;
        while(p&&i<index){
            p=p->next;
            i++;
        }
        if(p)return p->val;
        else return -1;
    }

    void addAtHead(int val){
        if(head!=nullptr){
            ListNode *node=new ListNode(val);
            node->next=head;
            head->prev=node;
            head=node;
        }
        else{
            head=new ListNode(val);
            tail=head;
        }
        ++size;
    }

    void addAtTail(int val){
        if(tail!=nullptr){
            ListNode *node=new ListNode(val);
            node->prev=tail;
            tail->next=node;
            tail=node;
        }
        else{
        	//尾节点为空,那么头节点也为空,然后首尾节点都为新节点
            tail=new ListNode(val);
            head=tail;
        }
        ++size;
    }

    void addAtIndex(int index,int val){
        //首先排除三种特殊情况的index,然后剩下来的index肯定在链表内
        if(index<=0){
            addAtHead(val);
            return;
        }
        if(index==size){
            addAtTail(val);
            return;
        }
        if(index>size)return;
        ListNode *p=nullptr,*cur=head;
        int i=0;
        while(cur&&i<index){
            p=cur;
            cur=cur->next;
            i++;
        }
        ListNode *node=new ListNode(val);
        //由于前面已经将特殊情况的index排除了,现在的p和cur都有效,都在链表内
        p->next=node;
        node->prev=p;
        node->next=cur;
        cur->prev=node;
        size++;
    }

    void deleteAtIndex(int index){
        //链表为空时,不能删除
        if(!head)return;
        if(index==0)
        {
            ListNode *del=head;
            head=head->next;
            if(head){//链表有2个以上节点
                head->prev=nullptr;
            }
            else{//链表只有一个节点,将尾部制空
                tail=nullptr;
            }
            delete del;
            size--;
            return;
        }
        //index为最后为尾节点,我们需要删除尾节点
        if(index==size-1){
            ListNode *del=tail;
            tail=tail->prev;
            //注意这里不用处理tail为空,因为tail为空的话,那么链表只有单个节点
            //然而单个节点只能删除0号节点,只有index为0时才能删除,
            //前面已经处理过了index为0的情况了,所以这里不在处理
            if(tail){
                tail->next=nullptr;
            }
            delete del;
            size--;
            return;
        }
        int i=0;
        ListNode *p=nullptr,*cur=head;
        while(cur){
            if(i==index){
                ListNode *del=cur;
                p->next=cur->next;
                if(cur->next){
                    cur->next->prev=p;
                }
                delete del;
                size--;
                return;
            }
            p=cur;
            cur=cur->next;
            ++i;
        }
    }

    int length(){
        return size;
    }
};

在这里插入图片描述

3、正文

双链表以类似的方式工作,但还有一个引用字段,称为“prev”字段。有了这个额外的字段,就能够知道当前结点的前一个结点。

首先初始化你的双链表:
在这里插入图片描述
如果想在给定的结点之后添加新值,分三种情况:

  • 头结点;
    在这里插入图片描述
  • 尾结点;
    在这里插入图片描述
  • 任意位置;
    在这里插入图片描述
    与单链表类似,添加操作的时间和空间复杂度都是 O(1)。
  • 删除现有结点
    在这里插入图片描述
    如果我们想从双链表中删除一个现有的结点 cur,我们可以简单地将它的前一个结点 prev 与下一个结点 next 链接起来。

与单链表不同,使用“prev”字段可以很容易地在常量时间内获得前一个结点。因为我们不再需要遍历链表来获取前一个结点,所以时间和空间复杂度都是O(1)。

在这里插入图片描述

4、实例

LeetCode 707,一个设计链表的题。
在这里插入图片描述
在这里插入图片描述
代码如上。

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */

在这里插入图片描述
在这里插入图片描述

如果有幸帮到你,请帮我点个【赞】,给个【关注】!如果能顺带【评论】给个鼓励,我将不胜感激。

如果想要更多的资源,欢迎关注 @我是管小亮,文字强迫症MAX~

手绘漫画】图解LeetCode之两两交换链中的节点(LeetCode 24)
文章目录图解LeetCode刷题计划1、写在前面2、题目3、正文4、代码 图解LeetCode刷题计划 1、写在前面 手绘漫画系列正式上线!!!“图解LeetCode刷题计划” 来了!!! 今天是第十九期,争取每天一期,最多两天一期,欢迎大家监督我。。。 2、题目 首先看一下题目, 【手绘漫画面试必考之图解逆转单链/单链逆序 这里要先确定一个问题,依旧还是逆转链, 不过是两个节点...
环形链进阶版【手绘漫画面试必考之双指针(LeetCode 142)
文章目录图解算法与数据结构1、前言2、实例3、正文4、代码 图解算法与数据结构 1、前言 今天开始的是双指针! 下面一起来看看吧!!! 让我们从一个经典问题开始: 给定一个链,判断链中是否有环。 你可能已经使用 哈希 提出了解决方案。但是,使用 双指针 技巧有一个更有效的解决方案。 想象一下,有两个速度不同的跑步者。如果他们在直路上行驶,快跑者将首先到达目的地。但是,如果它们在圆形跑...
手绘漫画面试必考之二分查找(解题模板深度剖析),中回
文章目录图解算法与数据结构1、????前言2、????代码3、????正文4、????实例 图解算法与数据结构 1、????前言 昨天更的二分查找,就是传统的二分查找模板,是存在一些问题的,在返回左边界还是右边界这个问题上,比较容易出错!!! 【手绘漫画面试必考之二分查找(解题模板深度剖析),上回 那么有没有什么百搭的模板? 下面一起来看看吧!!! 本次的模板应对重复元素也可以~ 下一期预计结合题目进行分析,争取一次...
手绘漫画面试必考单链解题模板深度剖析),(LeetCode 707)
文章目录图解算法与数据结构1、前言2、代码3、正文4、实例 图解算法与数据结构 1、前言 2、代码 模板: #include <iostream> using namespace std; //C++单向链模板 class MyListForward{ private: struct ListNode{ int val; ListNode *next; ListN...
手绘漫画面试必考之二分查找(解题模板深度剖析),上回
文章目录图解算法与数据结构1、????前言2、????代码3、????正文4、????实例 图解算法与数据结构 1、????前言 之所以断更了一天,就是因为上次说的这个二分查找,,,看的我心态多没了,之后就这阶段就一直刷二分查找了!!! 这是一个很经典的题目,【二分查找】问题。 初步上二分查找的时候,总觉得很简单,但是真的简单嘛??? 其实并不简单!!! 可以看看一些大佬关于二分查找法的论述: 算法和程序设计技术的...
再也不怕女朋友问我二分查找了!!!【手绘漫画面试必考之二分查找(解题模板深度剖析),最终回
文章目录1、前言2、万恶之源3、二分查找(LeetCode 704)4、x 的平方根(LeetCode 69)5、猜数字大小(LeetCode 374)6、搜索旋转排序数组(LeetCode 33)7、讨论 1、前言 今天是二分查找的最后一更,来做一下LeetCode中的探索的题~ 【手绘漫画面试必考之二分查找(解题模板深度剖析),上回 【手绘漫画面试必考之二分查找(解题模板深度剖析)...
??2020 CSDN 皮肤主题: 酷酷鲨 设计师:CSDN官方博客 返回首页