搜索内容

有一个问题?

如果您有任何疑问,可以在下面询问或输入您要寻找的!

单链表算法设计(含大厂面试题)

生成海报
Java硬件工程师
Java硬件工程师 2021-02-09 19:58
阅读需:0

文件目录

  • 1.单链表详细介绍与运行内存合理布局
  • 2.单链表的运用实例
    • 2.1 单链表的建立和解析xml的剖析完成
    • 2.2 单链表依照次序插进信息内容
    • 2.3 单链表节点的改动
    • 2.4 单链表节点的删掉
  • 3.大型厂面试问题
    • 3.1.搜索单链表中的倒数第k个节点(新浪网面试问题)
    • 3.2.单链表的翻转(腾讯面试题)
    • 3.3.从尾撞头复印单链表(百度搜索面试问题)

1.单链表详细介绍与运行内存合理布局

链表是井然有序的目录,可是它在运行内存中是储存以下:
在这里插入图片描述
总结:
1)链表是以连接点的方法来储存,是链条式储存
2)每一个连接点包括data域,next域: 偏向下一个连接点.
3)如图所示:发觉链表的每个连接点不一定是持续储存.
4)链表分带领连接点的链表和沒有头连接点的链表,依据具体的要求来明确

单链表(带领节点)逻辑性结构示意图以下
在这里插入图片描述

2.单链表的运用实例

应用带head头的单向链表完成-水浒英雄排名榜管理方法
1)进行对 英雄的增删实际操作,注: 删掉和改动,搜索.
2)第一 种方式 在加上英雄人物时,立即加上到链表的尾端
3)第二种方法在加上英雄人物时,依据排行将英雄人物插进到指定位置
(如果有这一排行,则加上不成功,并得出提醒)

2.1 单链表的建立和解析xml的剖析完成

单链表的建立平面图,表明单向链表的剖析

class HeroNode{
	int no;			//序号
	String name;
	String nickname;	//呢称
	HeroNode next;
}

加上(建立)
1.先建立一个head头连接点,功效便是表明单链表的头
2.后边大家每加上一个连接点,就立即添加到链表的最终
解析xml:
1.根据一个輔助自变量解析xml,协助解析xml全部链表
在这里插入图片描述
单链表分辨最后一个节点的方式 :分辨节点的next域是不是为空

下列编码完成链表插进和解析xml

//界定HeroNode,每一个HeroNode目标便是一个节点
class HeroNode{
    public int no;
    public String name;
    public String nickname;
    public HeroNode next;       //偏向下一个节点
    //构造器
    public HeroNode(int hNo,String hName,String hNickname){
        this.no=hNo;
        this.name=hName;
        this.nickname=hNickname;
    }
    //为了更好地表明方式 ,大家重写toString

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + '\'' +
                '}';
    }
}
//界定SingleLinkedList来管理方法真正的英雄
class SingleLinkedList{
    //先复位头节点,头节点不要动,不储放实际数据信息
    private HeroNode head=new HeroNode(0,"","");
    //加上节点到单向链表
    /*
    加上原素的情况下,最重要的便是要寻找链表的最后一个节点。(尾插法)。
    随后让最后一个节点的next域偏向全新的节点。
    * */
    //构思:当不考虑到序号次序时
    //1.寻找当今链表的最终节点
    //2.将最终节点的next域偏向新的节点就可以
    public void add(HeroNode heroNode){
        //由于head节点不可以动,因而大家必须一个輔助自变量
        HeroNode temp=head;
        //解析xml链表,寻找最终
        while(true){
            //寻找链表的最终
            if(temp.next==null){
                break;
            }
            //要是没有寻找最终,就将temp后退
            temp=temp.next;
        }
        //当撤出while循环系统时,temp就偏向了最终
        //将最终这一节点的next偏向新的节点
        temp.next=heroNode;
    }
    //表明链表[解析xml]
    public void list(){
        //先分辨链表是不是为空
        if(head.next==null){
            System.out.println("链表为空");
            return ;
        }
        //由于头节点不可以动,大家必须輔助自变量来比那边
        HeroNode temp=head.next;
        //假如temp所说节点不以空,那麼大家就可以复印
        while(temp!=null){
            System.out.println(temp);   //輸出节点信息内容
            temp=temp.next;     //一定当心,要后退,不然无限循环
        }
    }

}
public class SingleLinkedListDemo {
    public static void main(String[] args) {
        //开展检测
        //先建立节点
        HeroNode hero1=new HeroNode(1,"宋江","有利的");
        HeroNode hero2=new HeroNode(2,"卢俊义","玉麒麟");
        HeroNode hero3=new HeroNode(3,"吴用","智多星");
        HeroNode hero4=new HeroNode(4,"公孙胜","入云龙");
        //建立链表
        SingleLinkedList singleLinkedList=new SingleLinkedList();
        //添加
        singleLinkedList.add(hero1);
        singleLinkedList.add(hero4);
        singleLinkedList.add(hero2);
        singleLinkedList.add(hero3);
        //表明一把
        singleLinkedList.list();
    }
}

在这里插入图片描述
这时的次序是依照插进次序来键入的,怎样依照序号次序来輸出呢?

2.2 单链表依照次序插进信息内容

在这里插入图片描述
必须依照序号的次序加上
1.最先寻找新加上的连接点的部位,是根据輔助自变量(表针),根据遍历年来拿下
2.新的连接点.next =temp.next
3.将temp.next=新的连接点

//第二种方法在加上英雄人物时,依据排行将英雄人物插进到指定位置
    // (如果有这一排行,则加上不成功,并得出提醒)
    public void OrderAdd(HeroNode heroNode){
        //由于头节点不可以动,因而大家依然根据一个輔助表针(自变量)来协助寻找加上的部位
        //由于单链表,由于大家找的temp是坐落于加上部位的前一个节点,不然插进不上
        HeroNode temp=head;
        //假如temp.next==null,表明temp早已在链表的最终,表明加上的节点便是坐落于链表的最终
        while(temp.next!=null){
            //部位寻找,就在temp的后面
            if(temp.next.no>heroNode.no){
                break ;
            }else if(temp.next.no==heroNode.no){
               //不可以加上,表明序号存有
                System.out.println("提前准备插进的英雄人物的序号早已存有,不可以添加");
                return;
            }
            temp=temp.next;         //解析xml当今链表
        }
        heroNode.next=temp.next;
        temp.next=heroNode;
        return;
    }
//先建立节点
HeroNode hero1=new HeroNode(1,"宋江","有利的");
HeroNode hero2=new HeroNode(2,"卢俊义","玉麒麟");
HeroNode hero3=new HeroNode(3,"吴用","智多星");
HeroNode hero4=new HeroNode(4,"公孙胜","入云龙");
//建立链表
SingleLinkedList singleLinkedList=new SingleLinkedList();
//添加
singleLinkedList.OrderAdd(hero1);
singleLinkedList.OrderAdd(hero4);
singleLinkedList.OrderAdd(hero2);
singleLinkedList.OrderAdd(hero3);

在这里插入图片描述

2.3 单链表节点的改动

//改动节点的信息内容,依据no序号来改动,即no序号不可以改
    //表明:1.依据newHeroNode的no来改动
    public void update(HeroNode newHeroNode){
        //分辨是不是空
        if(head.next==null){
            System.out.println("链表为空");
            return;
        }
        //寻找必须改动的节点,依据no序号
        //界定一个輔助自变量
        HeroNode temp=head.next;
        while(temp!=null){
            if(temp.no==newHeroNode.no){
                System.out.println("找到");
                temp.nickname=newHeroNode.nickname;
                temp.name=newHeroNode.name;
                return;
            }
            temp=temp.next;
        }
        //早已解析xml完链表,可是还没找到
        System.out.printf("沒有寻找序号%d的节点",newHeroNode.no);
    }
//先建立节点
        HeroNode hero1=new HeroNode(1,"宋江","有利的");
        HeroNode hero2=new HeroNode(2,"卢俊义","玉麒麟");
        HeroNode hero3=new HeroNode(3,"吴用","智多星");
        HeroNode hero4=new HeroNode(4,"公孙胜","入云龙");
        //建立链表
        SingleLinkedList singleLinkedList=new SingleLinkedList();
        //添加
        singleLinkedList.OrderAdd(hero1);
        singleLinkedList.OrderAdd(hero4);
        singleLinkedList.OrderAdd(hero2);
        singleLinkedList.OrderAdd(hero3);

        //检测改动节点的编码
        HeroNode newHeroNode=new HeroNode(2,"小陈","玉麒麟~~");
        singleLinkedList.update(newHeroNode);

在这里插入图片描述

2.4 单链表节点的删掉

在这里插入图片描述
从单链表中删掉一个连接点的构思
1.大家先寻找必须删掉的这一连接点的前一个连接点temp
2. temp.next = temp.next.next
3.被删掉的连接点,将不容易有其他引入偏向,会被垃圾分类回收体制收购

//删掉节点
    //构思
    //1.head没动,因而大家必须一个temp輔助节点寻找待删掉节点的前一个节点
    //2.表明我们在较为时,是temp.next.no和必须删掉的节点的no开展较为
    public void delete(int no){
        HeroNode temp=head;
        //当解析xml到链表的最终,就务必撤出了
        while(temp.next!=null){
            //留意,我们要找的是待删掉节点的前一个节点
            if(temp.next.no==no){
                temp.next=temp.next.next;      //删掉节点
                return ;
            }
            temp=temp.next;     //后退才可以完成解析xml
        }
        //表明一直也没有寻找
        System.out.printf("沒有寻找特定的要删掉的序号为%d\n",no);
    }
		//检测删掉节点
        singleLinkedList.list();
        singleLinkedList.delete(3);
        System.out.println("删掉后");
        //表明一把
        singleLinkedList.list();

在这里插入图片描述

3.大型厂面试问题

3.1.搜索单链表中的倒数第k个节点(新浪网面试问题)

链表中倒数第k个节点

3.2.单链表的翻转(腾讯面试题)

反转链表

3.3.从尾撞头复印单链表(百度搜索面试问题)

从尾撞头复印链表

评论
  • 消灭零回复