文件目录

• 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.从尾撞头复印单链表（百度搜索面试问题）

从尾撞头复印链表