C++数据结构之链表详解

目录
  • 前言
    • 一、删除链表中给定值为key的节点
    • 二、反转链表
    • 三、返回链表的中间节点
    • 四、删除链表的倒数第K个节点
    • 五、分割链表
    • 六、合并两个有序链表
    • 七、删除有序链表中重复节点
    • 八、环形链表
    • 九、相交链表
    • 十、两数相加
    • 十一、回文链表
  • 总结

前言

链表类型的习题常用的技巧就是定义指针来代替head的,替head走,要么就是数学问题,环形链表就是利用数学思想取解决的,要么就是定义双指针来操作链表。

一、删除链表中给定值为key的节点

定义两个变量,一个使待删除的节点,一个为待删除节点的前驱节点,最后记得判断头节点是否为要删除的节点,最后返回头节点。

 public ListNode removeElements(ListNode head, int val) {
        if(head==null){
            return null;
        }
        ListNode cur=head.next;
        ListNode prev=head;
        while(cur!=null){
            if(cur.val==val){
                prev.next=cur.next;
            }else{
                prev=cur;
            }
            cur=cur.next;
        }
        if(head.val==val){
            head=head.next;
        }
        return head;
    }

二、反转链表

定义双指针法,类似于头插法,来将链表的节点头插法

cur节点是待反转的节点 curNext是保存下一个节点的地址值

1.先保存待反转节点下一个地址值,之后将头节点的next置空

2.只有用头插法将节点头插即可。

public ListNode reverseList(ListNode head) {
        //三指针法来反转链表
        if(head==null||head.next==null){
            return head;
        }
        ListNode cur=head;//要头插的节点
        ListNode curNext=head.next;//保存下一个节点的地址值
        cur=curNext;
        head.next=null;
        while(cur!=null){
            curNext=curNext.next;
            cur.next=head;
            head=cur;
            cur=curNext;
        }
        return head;
    }

三、返回链表的中间节点

定义快慢指针,注意偶数节点和奇数节点的情况

注意判断条件 在偶数情况下 如果是判断fast.next.next就会空指针异常,必须把判断条件两个都加上。

public ListNode middleNode(ListNode head) {
        //定义快慢指针 快指针比慢指针多走一步   注意奇数和偶数情况
        if(head==null||head.next==null){
            return head;
        }
        ListNode slow=head;
        ListNode fast=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        return slow;
    }

四、删除链表的倒数第K个节点

定义快慢指针 快指针先走n-1步 之后慢指针再走,修改地址值即可

public ListNode removeNthFromEnd(ListNode head, int n) {
        if(head==null){
            return null;
        }
        ListNode fast=head;
        ListNode dummy=new ListNode(0,head);
        ListNode slow=dummy;
        for(int i=1;i<n;i++){
            fast=fast.next;
        }
        while(fast.next!=null){
            fast=fast.next;
            slow=slow.next;
        }
        slow.next=slow.next.next;
        return dummy.next;
    }

五、分割链表

给定X值,分割链表 前面链表为小于X的值,后面链表为大于等于X的值
要考虑很多情况

1.第一次插入链表时 要将头节点和尾巴节点都指向插入的节点

2.不是第一次插入时,只需要把尾巴节点next值指向插入的节点,之后把尾巴节点往后挪

3.如果前面链表为空,返回后面链表的头

4。还需要将后面节点的next值置空,之后连接两个链表。

 public ListNode partition(ListNode head, int x) {
        //分割链表 将小于x的分为一部分,将大于等于x的分为一部分呢! 乖乖yy
        if(head==null){
            return null;
        }
        ListNode xh=null;//小于x的头节点
        ListNode xe=null;;//小于x的尾巴节点
        ListNode Xh=null;//大于等于X的头节点
        ListNode Xe=null;//大于等于X的尾节点
        ListNode cur=head;
        while(cur!=null){
            if(cur.val<x){
                //小于X的部分
                if(xh==null){
                    //第一次插入
                    xh=cur;
                    xe=cur;
                }else{
                    //不是第一次插入
                    xe.next=cur;
                    xe=cur;
                }
            }else{
                //>=X 的部分
                if(Xh==null){
                    //第一次插入
                    Xh=cur;
                    Xe=cur;
                }else{
                    //不是第一次插入
                    Xe.next=cur;
                    Xe=cur;
                }
            }
            cur=cur.next;
        }//判断 所有元素都大于x 前面的链表没有数据 要返回后面的链表
         if(xh==null){
            return Xh;
        }
        xe.next=Xh;
        if(Xh!=null){
            //将最后一个元素置为null
            Xe.next=null;
        }
        return xh;
    }

六、合并两个有序链表

和合并有序数组是一样的,链表复杂一些要将后面节点地址先保存,之后定义傀儡节点,按照值小的顺序连接起来

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    //1.思路就是先定傀儡节点,将链表穿起来 定义两个变量将后面地址保存起来 之后串糖葫芦一样串起来
    ListNode dummy=new ListNode(-1);
    ListNode head=dummy;//保存傀儡节点
    ListNode cur1=l1;//保存节点后面的地址值
    ListNode cur2=l2;
    while(l1!=null&&l2!=null){
        cur1=l1.next;
        cur2=l2.next;
        if(l1.val<=l2.val){
            dummy.next=l1;
            l1=cur1;
        }else{
            dummy.next=l2;
            l2=cur2;
        }
        dummy=dummy.next;
    }
    if(l1!=null){
        dummy.next=l1;
    }
    if(l2!=null){
        dummy.next=l2;
    }
    return head.next;
    }

七、删除有序链表中重复节点

双指针 遇到相等的就跳过 ,最后要将最后一个节点置为空。

 public ListNode deleteDuplicates(ListNode head) {
        if(head==null){
            return null;
        }
        ListNode prev=head;
        ListNode cur=head.next;
        while(cur!=null){
            if(prev.val==cur.val){
                cur=cur.next;
            }else{
                prev.next=cur;
                prev=cur;
                cur=cur.next;
            }
        }
        prev.next=cur;
        return head;
    }

八、环形链表

先用set判断是否存在 空间复杂度为O(N),不太符合题目要求

public boolean hasCycle(ListNode head) {
       HashSet<ListNode> set=new HashSet<>();
       while(head!=null){
           set.add(head);
           head=head.next;
           if(set.contains(head)){
               return true;
           }
       }
       return false;
    }

2.快慢指针数学问题,快指针走两步,慢指针走一步,有环一定相遇,没有环就不会相遇 空间复杂度为O(1)

 public boolean hasCycle(ListNode head) {
      //快慢指针还是数学问题
      if(head==null||head.next==null){
          return false;
      }
      ListNode slow=head;
      ListNode fast=head.next;
      while(slow!=fast){
          if(fast==null||fast.next==null){
              return false;
          }
          fast=fast.next.next;
          slow=slow.next;
      }
      return true;
    }

九、相交链表

1.先利用set存储节点 之后循环判断,空间复杂度为O(N)时间复杂度为O(N),比较慢

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        HashSet<ListNode>set=new HashSet<>();
        while(headA!=null){
            set.add(headA);
            headA=headA.next;
        }
        while(headB!=null){
            if(set.contains(headB)){
                return headB;
            }
            headB=headB.next;
        }
        return null;
    }

2.双指针,确实没想出来,看了题解才知道是两个链表相连接,遍历是否有想交的节点

 public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
      ListNode cur1=headA;
      ListNode cur2=headB;
      while(cur1!=cur2){
        cur1=cur1==null?headB:cur1.next;
        cur2=cur2==null?headA:cur2.next;
      }
       return cur1;
    }

十、两数相加

这道题没什么技巧,就是注意很多特殊情况,加完要判断进位,我第一次敲的时候能执行但是不能过,没有考虑到特殊情况。
最后看评论解答就是用一个进位标志数来解决,学到了。

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode list=new ListNode(-1);
        ListNode head=list;
        int t=0;
        while(l1!=null||l2!=null||t!=0){
            if(l1!=null){
                t+=l1.val;
                l1=l1.next;
            }
            if(l2!=null){
                t+=l2.val;
                l2=l2.next;
            }
            list.next=new ListNode(t%10);
            list=list.next;
            t/=10;
        }
        return head.next;
    }

十一、回文链表

1.可以将链表中值存放在顺序表中,之后定义双指针遍历判断

2.快慢指针带反转

3.利用栈实现li

public boolean isPalindrome(ListNode head) {
        //利用栈来实现回文结构
        Stack<Integer> stack=new Stack<>();
        ListNode cur=head;
        while(cur!=null){
            stack.push(cur.val);
            cur=cur.next;
        }
        ListNode cur1=head;
        while(cur1!=null){
            if(cur1.val!=stack.pop()){
                return false;
            }
            cur1=cur1.next;
        }
        return true;
    }

定义快慢指针,之后反转链表来实现

public boolean isPalindrome(ListNode head) {
        //快慢指针来反转链表
        if(head==null||head.next==null){
            return true;
        }
        ListNode fast=head;
        ListNode slow=head;
        while(fast.next!=null&&fast.next.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        //走到中间节点,反转链表
        slow=reverse(slow.next);
        while(slow!=null){
            if(head.val!=slow.val){
                return false;
            }
            head=head.next;
            slow=slow.next;
        }
        return true;
    }
    public ListNode reverse(ListNode head){
        //反转链表
        ListNode cur=head;
        ListNode curNext=head.next;
        cur=curNext;
        head.next=null;
        while(cur!=null){
            curNext=curNext.next;
            cur.next=head;
            head=cur;
            cur=curNext;
        }
        return head;
    }

总结

本篇文章就到这里了,希望能给你带来帮助,也希望你能给多多关注我们的更多内容!

(0)

相关推荐

  • C++数据结构与算法之反转链表的方法详解

    本文实例讲述了C++数据结构与算法之反转链表的方法.分享给大家供大家参考,具体如下: 算法概述:要求实现将一条单向链表反转并考虑时间复杂度. 算法分析: 数组法(略): 将列表元素逐个保存进数组,之后再逆向重建列表 点评:实现逻辑最简单,需要额外的内存开销. 移动指针: 通过三个指针逐个从链表头开始逐一反转链表元素的指针 点评:不需要额外的内存开销,会改变原始链表. 递归: 以递归的方式首先找到链表尾部,再逐一反转指针 点评:不需要额外的内存开销,不会改变原始链表. 算法实现: 构建链表结构 /

  • C++ 数据结构链表的实现代码

    C++ 链表 之前一直没怎么在意C++中的链表,但是突然一下子让自己写,就老是出错.没办法,决定好好恶补一下该方面的知识,也为今后的数据结构大下个良好的基础,于是我总结出以下几点,有些地方可能不正确,还望大家不吝赐教,旨在共同进步. 总结: 1.链表List的基本单元是节点Node,因此想要操作方便,就必须为每一步打好基础,Node的基本结构如下: class Node{ public: int data; Node *next; Node(int da=0,Node *p=NULL){ thi

  • C++ 数据结构之kmp算法中的求Next()函数的算法

    C++ 数据结构之kmp算法中的求Next()函数的算法 实例代码: #include <iostream> using namespace std; void preKmp(char *c, int m, int Next[]) { int i=1,j=-1; Next[0]=-2; while(i<m) { if(j==-2) { Next[i]=-1; i++; j=-1; } ++j; if(i==m) return; if(c[i]==c[j]) { Next[i]=j; ++

  • C++数据结构之链表的创建

    C++数据结构之链表的创建 前言 1.链表在C/C++里使用非常频繁, 因为它非常使用, 可作为天然的可变数组. push到末尾时对前面的链表项不影响. 反观C数组和std::vector, 一个是静态大小, 一个是增加多了会对之前的元素进行复制改写(线程非常不安全). 2.通常创建链表都是有next这样的成员变量指向下一个项, 通过定义一个head,last来进行链表创建. 参考函数 TestLinkCreateStupid(). 说明 1.其实很早就知道另一种创建方式, 但是一直没总结. 没

  • C++数据结构与算法之判断一个链表是否为回文结构的方法

    本文实例讲述了C++判断一个链表是否为回文结构的方法.分享给大家供大家参考,具体如下: 题目: 给定一个链表头节点head,请判断是否为回文结构 例如: 1->2->1 true 1->2->2->1 true 1->2->3->4->2->1 false 解题思路及代码 1.找到链表中间节点,然后将链表中间节点的右边所有节点放入一个栈中. 2.然后从链表首节点和栈顶元素一一对比,不相等则return false. 算法C++代码: 链表节点结构

  • Java数据结构之链表详解

    一.链表的介绍 什么是链表 链表是一种物理存储单元上非连续.非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的.链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成.每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域. 相比于线性表顺序结构,操作复杂.由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而线性表和顺序表相应的

  • Redis数据结构之链表详解

    目录 1 链表和链表节点的结构 2 链表相关的API 1 链表和链表节点的结构 1.1 节点结构 节点的结构大概长下边这个样子: 那么,把这些节点就连起来就成了这个样子: 1.2 链表结构 链表自然除了要把这些节点连起来,还得保存一些其他的信息,不然也太简单了,对吧.那么链表的结构大概长下边这个样子: head:指向链表的表头的指针tail:指向链表的表尾的指针len:记录链表的长度dup:函数用于复制链表节点所保存的值free:函数用于释放链表节点所保存的值match:函数则用于对比链表节点所

  • python数据结构之链表详解

    数据结构是计算机科学必须掌握的一门学问,之前很多的教材都是用C语言实现链表,因为c有指针,可以很方便的控制内存,很方便就实现链表,其他的语言,则没那么方便,有很多都是用模拟链表,不过这次,我不是用模拟链表来实现,因为python是动态语言,可以直接把对象赋值给新的变量. 好了,在说我用python实现前,先简单说说链表吧.在我们存储一大波数据时,我们很多时候是使用数组,但是当我们执行插入操作的时候就是非常麻烦,看下面的例子,有一堆数据1,2,3,5,6,7我们要在3和5之间插入4,如果用数组,我

  • C++数据结构之链表详解

    目录 前言 一.删除链表中给定值为key的节点 二.反转链表 三.返回链表的中间节点 四.删除链表的倒数第K个节点 五.分割链表 六.合并两个有序链表 七.删除有序链表中重复节点 八.环形链表 九.相交链表 十.两数相加 十一.回文链表 总结 前言 链表类型的习题常用的技巧就是定义指针来代替head的,替head走,要么就是数学问题,环形链表就是利用数学思想取解决的,要么就是定义双指针来操作链表. 一.删除链表中给定值为key的节点 定义两个变量,一个使待删除的节点,一个为待删除节点的前驱节点,

  • Java数据结构之单链表详解

    一.图示 二.链表的概念及结构 链表是一种物理存储结构上非连续存储结构,数据元素的逻辑顺序是通过链表中的引用链接次序实现的 . 实际中链表的结构非常多样,以下情况组合起来就有8种链表结构: 单向.双向 带头.不带头 循环.非循环 今天,我们实现的是一个 单向 无头 非循环的链表. 下面是此链表的结构组成. 三.单链表的实现 (1)定义一个节点类型 我们创建一个 ListNode 的类作为节点类型,那么我们如何定义成员属性呢? 通过上面的结构分析,我们需要定义两个成员变量 val --作为该节点的

  • C语言数据结构之单向链表详解分析

    链表的概念:链表是一种动态存储分布的数据结构,由若干个同一结构类型的结点依次串连而成. 链表分为单向链表和双向链表. 链表变量一般用指针head表示,用来存放链表首结点的地址. 每个结点由数据部分和下一个结点的地址部分组成,即每个结点都指向下一个结点.最后一个结点称为表尾,其下一个结点的地址部分的值为NULL(表示为空地址). 特别注意:链表中的各个结点在内存中是可以不连续存放的,具体存放位置由系统分配. 例如:int *ptr ; 因此不可以用ptr++的方式来寻找下一个结点. 使用链表的优点

  • Java语言实现数据结构栈代码详解

    近来复习数据结构,自己动手实现了栈.栈是一种限制插入和删除只能在一个位置上的表.最基本的操作是进栈和出栈,因此,又被叫作"先进后出"表. 首先了解下栈的概念: 栈是限定仅在表头进行插入和删除操作的线性表.有时又叫LIFO(后进先出表).要搞清楚这个概念,首先要明白"栈"原来的意思,如此才能把握本质. "栈"者,存储货物或供旅客住宿的地方,可引申为仓库.中转站,所以引入到计算机领域里,就是指数据暂时存储的地方,所以才有进栈.出栈的说法. 实现方式是

  • python实现单向链表详解

    本文研究的主要是Python中实现单向链表的相关内容,具体如下. 什么是链表 链表顾名思义就是-链 链表是一种动态数据结构,他的特点是用一组任意的存储单元存放数据元素.链表中每一个元素成为"结点",每一个结点都是由数据域和指针域组成的.跟数组不同链表不用预先定义大小,而且硬件支持的话可以无限扩展. 链表与数组的不同点: 数组需要预先定义大小,无法适应数据动态地增减,数据小于定义的长度会浪费内存,数据超过预定义的长度无法插入.而链表是动态增删数据,可以随意增加. 数组适用于获取元素的操作

  • redis中的数据结构和编码详解

    redis中的数据结构和编码:     背景: 1>redis在内部使用redisObject结构体来定义存储的值对象. 2>每种类型都有至少两种内部编码,Redis会根据当前值的类型和长度来决定使用哪种编码实现. 3>编码类型转换在Redis写入数据时自动完成,这个转换过程是不可逆的,转换规则只能从小内存编码向大内存编码转换.     源码: 值对象redisObject: typedef struct redisObject {                 unsigned ty

  • C语言链表详解及代码分析

    C语言链表详解附实例 什么是链表 链表是一种常见的重要的数据结构.它是动态地进行存储分配的一种结构.链表和数组比较,不用事先确定存储空间,而是根据需要开辟内存单元. 下图1是最简单的一种链表(单向链表)的结构 第 0 个结点称为头结点,它存放有第一个结点的首地址,它没有数据,只是一个指针变量.以下的每个结点都分为两个域,一个是数据域,存放各种实际的数据,如学号 num,姓名 name,性别 sex 和成绩 score 等.另一个域为指针域,存放下一结点的首地址.链表中的每一个结点都是同一种结构类

随机推荐