国内网站,漳州网站建设哪家最正规,建站开始的前6个月多少外链最合适,wordpress语言包更新文章目录 1. 链表介绍2. 单链表应用实例2.1. 顺序添加方式2.1.1. 思路分析2.1.2. 代码实现 2.2. 按照编号顺序添加方式2.2.1. 思路分析2.2.2. 代码实现 3. 单链表节点的修改3.1. 思路分析3.2. 代码实现 4. 单链表节点的删除4.1. 思路分析4.2. 代码实现 5. 单链表常见面试题5.1.… 文章目录 1. 链表介绍2. 单链表应用实例2.1. 顺序添加方式2.1.1. 思路分析2.1.2. 代码实现 2.2. 按照编号顺序添加方式2.2.1. 思路分析2.2.2. 代码实现 3. 单链表节点的修改3.1. 思路分析3.2. 代码实现 4. 单链表节点的删除4.1. 思路分析4.2. 代码实现 5. 单链表常见面试题5.1. 求单链表中有效节点的个数5.2. 查找单链表中倒数第k个节点5.3. 单链表的反转5.4. 从尾到头打印单链表 摘要在Java中可以使用类来实现链表结构每个节点作为类的实例包含数据和指向下一个节点的引用以及可能的前一个节点的引用对于双向链表。通过操作节点的引用可以实现链表的各种操作如插入、删除、查找等。 1. 链表介绍
相关概念 链表是一种常见的数据结构它由一系列节点组成每个节点包含数据部分和指向下一个节点的引用。链表有多种类型包括单向链表、双向链表和循环链表。
单向链表Singly Linked List每个节点包含数据和指向下一个节点的引用。 双向链表Doubly Linked List每个节点包含数据、指向前一个节点的引用和指向下一个节点的引用。 循环链表Circular Linked List尾节点指向头节点形成一个环形结构。 链表的优点之一是可以动态地分配内存空间而数组在创建时需要确定大小。然而链表的缺点包括不能随机访问元素需要从头开始逐个遍历而且需要额外的空间来存储指针。 链表是有序的列表但是它在内存中是存储如下 小结上图: 链表是以节点的方式来存储是链式存储 每个节点包含 data域 next域指向下一个节点如图发现链表的各个节点不一定是连续存储 链表分带头节点的链表和没有头节点的链表根据实际的需求来确定。 单链表(带头结点) 逻辑结构示意图如下 2. 单链表应用实例
使用带 head 头的单向链表实现 –水浒英雄排行榜管理完成对英雄人物的增、删、改、查操作。有两种方式实现解释如下
给链表中的数据加入编号属性加入需要添加4个链表数据其编号分别为1、2、3、4。 ①按照添加顺序顺序添加方式根据添加的顺序依次加入到链表中如添加顺序是1、4、2、3在链表中的顺序也是1、4、2、3。 ②按照编号顺序编号顺序添加方式对加入链表中数据进行编号根据编号进行排序如添加的顺序是1、4、2、3而在链表中会按照1、2、3、4编号顺序
2.1. 顺序添加方式
2.1.1. 思路分析
第一种方法在添加英雄时直接添加到链表的尾部
思路分析示意图 2.1.2. 代码实现 按照加入的先后顺序形成链表 package linkedlist;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(hero2);singleLinkedList.add(hero3);singleLinkedList.add(hero4);//显示singleLinkedList.list();}
}//定义SingleLinkedList 管理我们的英雄人物
class SingleLinkedList{//先初始化一个头节点头节点不要动,不存放具体的数据private HeroNode head new HeroNode(0, null, null);//添加节点到单向链表//思路当不考虑编号顺序时//1. 找到当前链表的最后节点//2. 将最后这个节点的next指向新的节点public void add (HeroNode heroNode){//因为head节点不能动因此我们需要一个辅助遍历tempHeroNode temp head;//遍历链表找到最后while (true) {//找到链表最后if(temp.next null){break;}//如果没有找到 最后将temp后移temp temp.next;}//当退出while循环时temp就指向了链表的最后//将最后这个节点的next 指向 新的节点temp.next heroNode;}//显示链表[遍历]public void list(){//先判断链表是否为空if(head.next null){System.out.println(链表为空);return;}//因为头节点不能动每个HeroNode对象就是一个节点HeroNode temp head.next;while (true) {//判断是否到链表最后if(temp null){break;}//输出节点的信息System.out.println(temp);//将next后移。不后移就成了死循环一定小心temp temp.next;}}
}//定义一个 HeroNode每个 HeroNode 对象就是一个节点
class HeroNode{public int no;public String name;public String nickname;public HeroNode next;//指向下一个节点//构造器public HeroNode(int No, String Name, String Nickname){this.no No;this.name Name;this.nickname Nickname;}//为了显示方便我们重写toStringOverridepublic String toString() {// return HeroNode [no no , name name , nickname nickname , next next ];return HeroNode [no no , name name , nickname nickname ];}}运行结果 2.2. 按照编号顺序添加方式
2.2.1. 思路分析
第二种方式在添加英雄时根据排名将英雄插入到指定位置(如果有这个排名则添加失败并给出提示)
思路的分析示意图 按照编号的顺序添加 首先找到新添加的节点的位置, 是通过辅助变量(指针), 通过遍历来搞定新的节点.next temp.next将temp.next 新的节点 2.2.2. 代码实现
package linkedlist;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.addByOrder(hero1);singleLinkedList.addByOrder(hero4);singleLinkedList.addByOrder(hero2);singleLinkedList.addByOrder(hero3);singleLinkedList.addByOrder(hero3);//显示singleLinkedList.list();}
}//定义SingleLinkedList 管理我们的英雄人物
class SingleLinkedList{//先初始化一个头节点头节点不要动,不存放具体的数据private HeroNode head new HeroNode(0, null, null);//添加节点到单向链表//思路当不考虑编号顺序时//1. 找到当前链表的最后节点//2. 将最后这个节点的next指向新的节点public void add (HeroNode heroNode){//因为head节点不能动因此我们需要一个辅助遍历tempHeroNode temp head;//遍历链表找到最后while (true) {//找到链表最后if(temp.next null){break;}//如果没有找到 最后将temp后移temp temp.next;}//当退出while循环时temp就指向了链表的最后//将最后这个节点的next 指向 新的节点temp.next heroNode;}//第二种方式在添加英雄时根据排名将英雄插入到指定位置//如果有这个排名则添加失败并给出提示public void addByOrder(HeroNode heroNode){//因为头节点不能动因此我们仍然通过一个辅助指针变量来帮助找到添加的位置//因为单列表我们找的temp是位于添加位置的前一个节点否则插入不了HeroNode temp head;boolean flag false;//标识添加的编号是否已经存在默认为falsewhile (true) {if(temp.next null){//说明temp已经在链表的最后break;}if(temp.next.no heroNode.no){//位置找到就在temp的后面插入break;}else if (temp.next.no heroNode.no) {//说明希望添加的heroNode的编号已经存在flag true;//说明编号存在break;}temp temp.next;//后移遍历当前链表}//判断flag的值if (flag) {//不能添加说明编号存在System.out.printf(准备插入的英雄编号 %d 已经存在了不能添加\n, heroNode.no);}else{//插入到链表中temp的后面heroNode.next temp.next;temp.next heroNode;}}//显示链表[遍历]public void list(){//先判断链表是否为空if(head.next null){System.out.println(链表为空);return;}//因为头节点不能动每个HeroNode对象就是一个节点HeroNode temp head.next;while (true) {//判断是否到链表最后if(temp null){break;}//输出节点的信息System.out.println(temp);//将next后移。不后移就成了死循环一定小心temp temp.next; }}
}//定义一个 HeroNode每个 HeroNode 对象就是一个节点
class HeroNode{public int no;public String name;public String nickname;public HeroNode next;//指向下一个节点//构造器public HeroNode(int No, String Name, String Nickname){this.no No;this.name Name;this.nickname Nickname;}//为了显示方便我们重写toStringOverridepublic String toString() {// return HeroNode [no no , name name , nickname nickname , next next ];return HeroNode [no no , name name , nickname nickname ];}
}上述代码添加的顺序是按照节点1、4、2、3、3的顺序添加最后实现的结果是按照编号的顺序添加并且如果重复添加会给出重复信息。 运行结果 3. 单链表节点的修改
3.1. 思路分析
思路 (1) 先找到该节点通过遍历 (2) temp.name newHeroNode.name ; temp.nickname newHeroNode.nicknam
3.2. 代码实现
package Linkedlist;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.addByOrder(hero1);singleLinkedList.addByOrder(hero4);singleLinkedList.addByOrder(hero2);singleLinkedList.addByOrder(hero3);// singleLinkedList.addByOrder(hero3);//显示一把singleLinkedList.list();//测试修改节点的代码HeroNode newHeroNode new HeroNode(2, 小卢, 玉麒麟~~);singleLinkedList.update(newHeroNode);System.out.println(修改后的链表情况~~);singleLinkedList.list();}
}//定义SingleLinkedList 管理我们的英雄人物
class SingleLinkedList{//先初始化一个头节点头节点不要动,不存放具体的数据private HeroNode head new HeroNode(0, null, null);//添加节点到单向链表//思路当不考虑编号顺序时//1. 找到当前链表的最后节点//2. 将最后这个节点的next指向新的节点public void add (HeroNode heroNode){//因为head节点不能动因此我们需要一个辅助遍历tempHeroNode temp head;//遍历链表找到最后while (true) {//找到链表最后if(temp.next null){break;}//如果没有找到 最后将temp后移temp temp.next;}//当退出while循环时temp就指向了链表的最后//将最后这个节点的next 指向 新的节点temp.next heroNode;}//第二种方式在添加英雄时根据排名将英雄插入到指定位置//如果有这个排名则添加失败并给出提示public void addByOrder(HeroNode heroNode){//因为头节点不能动因此我们仍然通过一个辅助指针变量来帮助找到添加的位置//因为单列表我们找的temp是位于添加位置的前一个节点否则插入不了HeroNode temp head;boolean flag false;//标识添加的编号是否已经存在默认为falsewhile (true) {if(temp.next null){//说明temp已经在链表的最后break;}if(temp.next.no heroNode.no){//位置找到就在temp的后面插入break;}else if (temp.next.no heroNode.no) {//说明希望添加的heroNode的编号已经存在flag true;//说明编号存在break;}temp temp.next;//后移遍历当前链表}//判断flag的值if (flag) {//不能添加说明编号存在System.out.printf(准备插入的英雄编号 %d 已经存在了不能添加\n, heroNode.no);}else{//插入到链表中temp的后面heroNode.next temp.next;temp.next heroNode;}}//修改节点的信息, 根据 no 编号来修改即 no 编号不能改. //说明//1. 根据 newHeroNode 的 no 来修改即可public void update(HeroNode newHeroNode) {//判断是否空if(head.next null) {System.out.println(链表为空~);return;}//找到需要修改的节点, 根据 no 编号//定义一个辅助变量HeroNode temp head.next;boolean flag false; //表示是否找到该节点while(true) {if (temp null) {break; //已经遍历完链表}if(temp.no newHeroNode.no) {//找到flag true;break;}temp temp.next;}//根据 flag 判断是否找到要修改的节点if(flag) {temp.name newHeroNode.name;temp.nickname newHeroNode.nickname;} else { //没有找到System.out.printf(没有找到 编号 %d 的节点不能修改\n, newHeroNode.no);}}//显示链表[遍历]public void list(){//先判断链表是否为空if(head.next null){System.out.println(链表为空);return;}//因为头节点不能动每个HeroNode对象就是一个节点HeroNode temp head.next;while (true) {//判断是否到链表最后if(temp null){break;}//输出节点的信息System.out.println(temp);//将next后移。不后移就成了死循环一定小心temp temp.next; }}
}//定义一个 HeroNode每个 HeroNode 对象就是一个节点
class HeroNode{public int no;public String name;public String nickname;public HeroNode next;//指向下一个节点//构造器public HeroNode(int No, String Name, String Nickname){this.no No;this.name Name;this.nickname Nickname;}//为了显示方便我们重写toStringOverridepublic String toString() {// return HeroNode [no no , name name , nickname nickname , next next ];return HeroNode [no no , name name , nickname nickname ];}
}运行结果 4. 单链表节点的删除
4.1. 思路分析
思路分析示意图 从单链表中删除一个节点的思路 先找到 需要删除的这个节点的前一个节点 temptemp.next temp.next.next被删除的节点将不会有其它引用指向会被垃圾回收机制回收 4.2. 代码实现
package Linkedlist;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.addByOrder(hero1);singleLinkedList.addByOrder(hero4);singleLinkedList.addByOrder(hero2);singleLinkedList.addByOrder(hero3);// singleLinkedList.addByOrder(hero3);//显示一把singleLinkedList.list();//测试修改节点的代码HeroNode newHeroNode new HeroNode(2, 小卢, 玉麒麟~~);singleLinkedList.update(newHeroNode);System.out.println(修改后的链表情况~~);singleLinkedList.list();//删除一个节点System.out.println(删除后的链表情况~~);singleLinkedList.del(1);singleLinkedList.del(4);singleLinkedList.del(2);singleLinkedList.del(3);singleLinkedList.list();}
}//定义SingleLinkedList 管理我们的英雄人物
class SingleLinkedList{//先初始化一个头节点头节点不要动,不存放具体的数据private HeroNode head new HeroNode(0, null, null);//添加节点到单向链表//思路当不考虑编号顺序时//1. 找到当前链表的最后节点//2. 将最后这个节点的next指向新的节点public void add (HeroNode heroNode){//因为head节点不能动因此我们需要一个辅助遍历tempHeroNode temp head;//遍历链表找到最后while (true) {//找到链表最后if(temp.next null){break;}//如果没有找到 最后将temp后移temp temp.next;}//当退出while循环时temp就指向了链表的最后//将最后这个节点的next 指向 新的节点temp.next heroNode;}//第二种方式在添加英雄时根据排名将英雄插入到指定位置//如果有这个排名则添加失败并给出提示public void addByOrder(HeroNode heroNode){//因为头节点不能动因此我们仍然通过一个辅助指针变量来帮助找到添加的位置//因为单列表我们找的temp是位于添加位置的前一个节点否则插入不了HeroNode temp head;boolean flag false;//标识添加的编号是否已经存在默认为falsewhile (true) {if(temp.next null){//说明temp已经在链表的最后break;}if(temp.next.no heroNode.no){//位置找到就在temp的后面插入break;}else if (temp.next.no heroNode.no) {//说明希望添加的heroNode的编号已经存在flag true;//说明编号存在break;}temp temp.next;//后移遍历当前链表}//判断flag的值if (flag) {//不能添加说明编号存在System.out.printf(准备插入的英雄编号 %d 已经存在了不能添加\n, heroNode.no);}else{//插入到链表中temp的后面heroNode.next temp.next;temp.next heroNode;}}//修改节点的信息, 根据 no 编号来修改即 no 编号不能改. //说明//1. 根据 newHeroNode 的 no 来修改即可public void update(HeroNode newHeroNode) {//判断是否空if(head.next null) {System.out.println(链表为空~);return;}//找到需要修改的节点, 根据 no 编号//定义一个辅助变量HeroNode temp head.next;boolean flag false; //表示是否找到该节点while(true) {if (temp null) {break; //已经遍历完链表}if(temp.no newHeroNode.no) {//找到flag true;break;}temp temp.next;}//根据 flag 判断是否找到要修改的节点if(flag) {temp.name newHeroNode.name;temp.nickname newHeroNode.nickname;} else { //没有找到System.out.printf(没有找到 编号 %d 的节点不能修改\n, newHeroNode.no);}}//删除节点//思路//1. head 不能动因此我们需要一个temp辅助节点找到待删除节点的前一个节//2. 说明我们在比较时是temp.next.no 和 需要删除的节点的no比较public void del(int no){HeroNode temp head;boolean flag false;//标识是否找到待删除的节点while(true){if(temp.next null){//已经到链表的最后break;}if(temp.next.no no){//找到的待刪除节点的前一个节点tempflag true;break;}temp temp.next;//temp后移}//判断flagif(flag){//找到//可以删除temp.next temp.next.next;}else{System.out.printf(要删除的 %d 节点不存在\n, no);}}//显示链表[遍历]public void list(){//先判断链表是否为空if(head.next null){System.out.println(链表为空);return;}//因为头节点不能动每个HeroNode对象就是一个节点HeroNode temp head.next;while (true) {//判断是否到链表最后if(temp null){break;}//输出节点的信息System.out.println(temp);//将next后移。不后移就成了死循环一定小心temp temp.next; }}
}//定义一个 HeroNode每个 HeroNode 对象就是一个节点
class HeroNode{public int no;public String name;public String nickname;public HeroNode next;//指向下一个节点//构造器public HeroNode(int No, String Name, String Nickname){this.no No;this.name Name;this.nickname Nickname;}//为了显示方便我们重写toStringOverridepublic String toString() {// return HeroNode [no no , name name , nickname nickname , next next ];return HeroNode [no no , name name , nickname nickname ];}
}运行结果
5. 单链表常见面试题
5.1. 求单链表中有效节点的个数
功能实现
//方法获取单链表的节点个数如果是带头节点的链表那么久不统计头节点/*** * param head* return*/public static int getLength(HeroNode head){if(head.next null){//空链表return 0;}int length 0;//定义一个辅助变量,没有统计头节点HeroNode cur head.next;while(cur ! null) {length;cur cur.next;//遍历}return length;}完整代码实现
package Linkedlist;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.addByOrder(hero1);singleLinkedList.addByOrder(hero4);singleLinkedList.addByOrder(hero2);singleLinkedList.addByOrder(hero3);// singleLinkedList.addByOrder(hero3);//显示一把singleLinkedList.list();//测试修改节点的代码HeroNode newHeroNode new HeroNode(2, 小卢, 玉麒麟~~);singleLinkedList.update(newHeroNode);System.out.println(修改后的链表情况~~);singleLinkedList.list();//删除一个节点System.out.println(删除后的链表情况~~);singleLinkedList.del(1);singleLinkedList.del(4);
// singleLinkedList.del(2);
// singleLinkedList.del(3);singleLinkedList.list();//求单链表中有效节点个数System.out.println(有效的节点个数 getLength(singleLinkedList.getHead()));}//方法获取单链表的节点个数如果是带头节点的链表那么久不统计头节点/*** * param head* return*/public static int getLength(HeroNode head){if(head.next null){//空链表return 0;}int length 0;//定义一个辅助变量,没有统计头节点HeroNode cur head.next;while(cur ! null) {length;cur cur.next;//遍历}return length;}
}//定义SingleLinkedList 管理我们的英雄人物
class SingleLinkedList{//先初始化一个头节点头节点不要动,不存放具体的数据private HeroNode head new HeroNode(0, null, null);//返回头节点public HeroNode getHead() {return head;}//添加节点到单向链表//思路当不考虑编号顺序时//1. 找到当前链表的最后节点//2. 将最后这个节点的next指向新的节点public void add (HeroNode heroNode){//因为head节点不能动因此我们需要一个辅助遍历tempHeroNode temp head;//遍历链表找到最后while (true) {//找到链表最后if(temp.next null){break;}//如果没有找到 最后将temp后移temp temp.next;}//当退出while循环时temp就指向了链表的最后//将最后这个节点的next 指向 新的节点temp.next heroNode;}//第二种方式在添加英雄时根据排名将英雄插入到指定位置//如果有这个排名则添加失败并给出提示public void addByOrder(HeroNode heroNode){//因为头节点不能动因此我们仍然通过一个辅助指针变量来帮助找到添加的位置//因为单列表我们找的temp是位于添加位置的前一个节点否则插入不了HeroNode temp head;boolean flag false;//标识添加的编号是否已经存在默认为falsewhile (true) {if(temp.next null){//说明temp已经在链表的最后break;}if(temp.next.no heroNode.no){//位置找到就在temp的后面插入break;}else if (temp.next.no heroNode.no) {//说明希望添加的heroNode的编号已经存在flag true;//说明编号存在break;}temp temp.next;//后移遍历当前链表}//判断flag的值if (flag) {//不能添加说明编号存在System.out.printf(准备插入的英雄编号 %d 已经存在了不能添加\n, heroNode.no);}else{//插入到链表中temp的后面heroNode.next temp.next;temp.next heroNode;}}//修改节点的信息, 根据 no 编号来修改即 no 编号不能改. //说明//1. 根据 newHeroNode 的 no 来修改即可public void update(HeroNode newHeroNode) {//判断是否空if(head.next null) {System.out.println(链表为空~);return;}//找到需要修改的节点, 根据 no 编号//定义一个辅助变量HeroNode temp head.next;boolean flag false; //表示是否找到该节点while(true) {if (temp null) {break; //已经遍历完链表}if(temp.no newHeroNode.no) {//找到flag true;break;}temp temp.next;}//根据 flag 判断是否找到要修改的节点if(flag) {temp.name newHeroNode.name;temp.nickname newHeroNode.nickname;} else { //没有找到System.out.printf(没有找到 编号 %d 的节点不能修改\n, newHeroNode.no);}}//删除节点//思路//1. head 不能动因此我们需要一个temp辅助节点找到待删除节点的前一个节//2. 说明我们在比较时是temp.next.no 和 需要删除的节点的no比较public void del(int no){HeroNode temp head;boolean flag false;//标识是否找到待删除的节点while(true){if(temp.next null){//已经到链表的最后break;}if(temp.next.no no){//找到的待刪除节点的前一个节点tempflag true;break;}temp temp.next;//temp后移}//判断flagif(flag){//找到//可以删除temp.next temp.next.next;}else{System.out.printf(要删除的 %d 节点不存在\n, no);}}//显示链表[遍历]public void list(){//先判断链表是否为空if(head.next null){System.out.println(链表为空);return;}//因为头节点不能动每个HeroNode对象就是一个节点HeroNode temp head.next;while (true) {//判断是否到链表最后if(temp null){break;}//输出节点的信息System.out.println(temp);//将next后移。不后移就成了死循环一定小心temp temp.next; }}
}//定义一个 HeroNode每个 HeroNode 对象就是一个节点
class HeroNode{public int no;public String name;public String nickname;public HeroNode next;//指向下一个节点//构造器public HeroNode(int No, String Name, String Nickname){this.no No;this.name Name;this.nickname Nickname;}//为了显示方便我们重写toStringOverridepublic String toString() {// return HeroNode [no no , name name , nickname nickname , next next ];return HeroNode [no no , name name , nickname nickname ];}
}运行结果 5.2. 查找单链表中倒数第k个节点
新浪面试题 功能实现 //查找单链表中的倒数第k个节点【新浪面试题】//思路//1. 编写一个方法接收head节点同时接收一个index//2. index 表示是倒数第index个节点//3. 先把链表从头到尾遍历得到链表的总长度getLength//4. 得到size(getLength)后我们从链表的第一个开始遍历size-index个就可以得到//5. 如果找到了则返回该节点否则返回nullpublic static HeroNode findLastIndexNode(HeroNode head, int index){//判断如果链表为空返回nullif(head.next null){return null;//没有找到}//第一次遍历得到链表的长度节点个数int size getLength(head);//第二次遍历 size-index 位置//先做一个index的校验if(index 0 || index size){return null;}//定义一个辅助变量,for循环定位到倒数的indexHeroNode cur head.next;//假设链表有3个数据查找倒数第一个数据那么size-index3-12for(int i 0; i size - index; i){cur cur.next;}return cur;}完整代码实现
package Linkedlist;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.addByOrder(hero1);singleLinkedList.addByOrder(hero4);singleLinkedList.addByOrder(hero2);singleLinkedList.addByOrder(hero3);// singleLinkedList.addByOrder(hero3);//显示链表singleLinkedList.list();System.out.println(--------------------------------);//查找倒数第k个节点HeroNode result findLastIndexNode(singleLinkedList.getHead(), 1);System.out.println(result result);}//查找单链表中的倒数第k个节点【新浪面试题】//思路//1. 编写一个方法接收head节点同时接收一个index//2. index 表示是倒数第index个节点//3. 先把链表从头到尾遍历得到链表的总长度getLength//4. 得到size(getLength)后我们从链表的第一个开始遍历size-index个就可以得到//5. 如果找到了则返回该节点否则返回nullpublic static HeroNode findLastIndexNode(HeroNode head, int index){//判断如果链表为空返回nullif(head.next null){return null;//没有找到}//第一次遍历得到链表的长度节点个数int size getLength(head);//第二次遍历 size-index 位置//先做一个index的校验if(index 0 || index size){return null;}//定义一个辅助变量,for循环定位到倒数的indexHeroNode cur head.next;//假设链表有3个数据查找倒数第一个数据那么size-index3-12for(int i 0; i size - index; i){cur cur.next;}return cur;}//方法获取单链表的节点个数如果是带头节点的链表那么久不统计头节点/*** * param head* return*/public static int getLength(HeroNode head){if(head.next null){//空链表return 0;}int length 0;//定义一个辅助变量,没有统计头节点HeroNode cur head.next;while(cur ! null) {length;cur cur.next;//遍历}return length;}
}//定义SingleLinkedList 管理我们的英雄人物
class SingleLinkedList{//先初始化一个头节点头节点不要动,不存放具体的数据private HeroNode head new HeroNode(0, null, null);//返回头节点public HeroNode getHead() {return head;}//添加节点到单向链表//思路当不考虑编号顺序时//1. 找到当前链表的最后节点//2. 将最后这个节点的next指向新的节点public void add (HeroNode heroNode){//因为head节点不能动因此我们需要一个辅助遍历tempHeroNode temp head;//遍历链表找到最后while (true) {//找到链表最后if(temp.next null){break;}//如果没有找到 最后将temp后移temp temp.next;}//当退出while循环时temp就指向了链表的最后//将最后这个节点的next 指向 新的节点temp.next heroNode;}//第二种方式在添加英雄时根据排名将英雄插入到指定位置//如果有这个排名则添加失败并给出提示public void addByOrder(HeroNode heroNode){//因为头节点不能动因此我们仍然通过一个辅助指针变量来帮助找到添加的位置//因为单列表我们找的temp是位于添加位置的前一个节点否则插入不了HeroNode temp head;boolean flag false;//标识添加的编号是否已经存在默认为falsewhile (true) {if(temp.next null){//说明temp已经在链表的最后break;}if(temp.next.no heroNode.no){//位置找到就在temp的后面插入break;}else if (temp.next.no heroNode.no) {//说明希望添加的heroNode的编号已经存在flag true;//说明编号存在break;}temp temp.next;//后移遍历当前链表}//判断flag的值if (flag) {//不能添加说明编号存在System.out.printf(准备插入的英雄编号 %d 已经存在了不能添加\n, heroNode.no);}else{//插入到链表中temp的后面heroNode.next temp.next;temp.next heroNode;}}//修改节点的信息, 根据 no 编号来修改即 no 编号不能改. //说明//1. 根据 newHeroNode 的 no 来修改即可public void update(HeroNode newHeroNode) {//判断是否空if(head.next null) {System.out.println(链表为空~);return;}//找到需要修改的节点, 根据 no 编号//定义一个辅助变量HeroNode temp head.next;boolean flag false; //表示是否找到该节点while(true) {if (temp null) {break; //已经遍历完链表}if(temp.no newHeroNode.no) {//找到flag true;break;}temp temp.next;}//根据 flag 判断是否找到要修改的节点if(flag) {temp.name newHeroNode.name;temp.nickname newHeroNode.nickname;} else { //没有找到System.out.printf(没有找到 编号 %d 的节点不能修改\n, newHeroNode.no);}}//删除节点//思路//1. head 不能动因此我们需要一个temp辅助节点找到待删除节点的前一个节//2. 说明我们在比较时是temp.next.no 和 需要删除的节点的no比较public void del(int no){HeroNode temp head;boolean flag false;//标识是否找到待删除的节点while(true){if(temp.next null){//已经到链表的最后break;}if(temp.next.no no){//找到的待刪除节点的前一个节点tempflag true;break;}temp temp.next;//temp后移}//判断flagif(flag){//找到//可以删除temp.next temp.next.next;}else{System.out.printf(要删除的 %d 节点不存在\n, no);}}//显示链表[遍历]public void list(){//先判断链表是否为空if(head.next null){System.out.println(链表为空);return;}//因为头节点不能动每个HeroNode对象就是一个节点HeroNode temp head.next;while (true) {//判断是否到链表最后if(temp null){break;}//输出节点的信息System.out.println(temp);//将next后移。不后移就成了死循环一定小心temp temp.next; }}
}//定义一个 HeroNode每个 HeroNode 对象就是一个节点
class HeroNode{public int no;public String name;public String nickname;public HeroNode next;//指向下一个节点//构造器public HeroNode(int No, String Name, String Nickname){this.no No;this.name Name;this.nickname Nickname;}//为了显示方便我们重写toStringOverridepublic String toString() {// return HeroNode [no no , name name , nickname nickname , next next ];return HeroNode [no no , name name , nickname nickname ];}
}运行结果 5.3. 单链表的反转
腾讯面试题 分析思路 将原来链表中的第一个节点放到新链表的第一个位置节点head后面然后将原来第二个节点放到新链表的第一个位置这样图中的数据5就在数据2前面了再将数据5的next指向数据2。同理插入数据9。最后形成的新链表就是原链表反转的结果。 功能实现 //将单链表反转public static void reversetList(HeroNode head){//如果当前链表为空或者只有一个节点无需反转直接返回if(head.next null || head.next.next null){return;}//定义一个辅助的指针变量帮助我们遍历原来的链表HeroNode cur head.next;HeroNode next null;//指向当前节点[cur]的下一个节点HeroNode reverseHead new HeroNode(0, , );//遍历原来的链表每遍历一个节点就将其取出并放在新的链表reverseHead 的最前端while (cur ! null) {next cur.next;//先暂时保存当前节点的下一个节点后面需要使用cur.next reverseHead.next;//将cur的下一个节点指向新的链表的最前端reverseHead.next cur;cur next;//让cur后移}//将head.next 指向reverseHead.next实现单链表的反转head.next reverseHead.next;}完整代码实现
package Linkedlist;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.addByOrder(hero1);singleLinkedList.addByOrder(hero4);singleLinkedList.addByOrder(hero2);singleLinkedList.addByOrder(hero3);// singleLinkedList.addByOrder(hero3);//显示链表singleLinkedList.list();System.out.println(--------------------------------);reversetList(singleLinkedList.getHead());singleLinkedList.list();}//将单链表反转public static void reversetList(HeroNode head){//如果当前链表为空或者只有一个节点无需反转直接返回if(head.next null || head.next.next null){return;}//定义一个辅助的指针变量帮助我们遍历原来的链表HeroNode cur head.next;HeroNode next null;//指向当前节点[cur]的下一个节点HeroNode reverseHead new HeroNode(0, , );//遍历原来的链表每遍历一个节点就将其取出并放在新的链表reverseHead 的最前端while (cur ! null) {next cur.next;//先暂时保存当前节点的下一个节点后面需要使用cur.next reverseHead.next;//将cur的下一个节点指向新的链表的最前端reverseHead.next cur;cur next;//让cur后移}//将head.next 指向reverseHead.next实现单链表的反转head.next reverseHead.next;}//查找单链表中的倒数第k个节点【新浪面试题】//思路//1. 编写一个方法接收head节点同时接收一个index//2. index 表示是倒数第index个节点//3. 先把链表从头到尾遍历得到链表的总长度getLength//4. 得到size(getLength)后我们从链表的第一个开始遍历size-index个就可以得到//5. 如果找到了则返回该节点否则返回nullpublic static HeroNode findLastIndexNode(HeroNode head, int index){//判断如果链表为空返回nullif(head.next null){return null;//没有找到}//第一次遍历得到链表的长度节点个数int size getLength(head);//第二次遍历 size-index 位置//先做一个index的校验if(index 0 || index size){return null;}//定义一个辅助变量,for循环定位到倒数的indexHeroNode cur head.next;//假设链表有3个数据查找倒数第一个数据那么size-index3-12for(int i 0; i size - index; i){cur cur.next;}return cur;}//方法获取单链表的节点个数如果是带头节点的链表那么久不统计头节点/*** * param head* return*/public static int getLength(HeroNode head){if(head.next null){//空链表return 0;}int length 0;//定义一个辅助变量,没有统计头节点HeroNode cur head.next;while(cur ! null) {length;cur cur.next;//遍历}return length;}
}//定义SingleLinkedList 管理我们的英雄人物
class SingleLinkedList{//先初始化一个头节点头节点不要动,不存放具体的数据private HeroNode head new HeroNode(0, null, null);//返回头节点public HeroNode getHead() {return head;}//添加节点到单向链表//思路当不考虑编号顺序时//1. 找到当前链表的最后节点//2. 将最后这个节点的next指向新的节点public void add (HeroNode heroNode){//因为head节点不能动因此我们需要一个辅助遍历tempHeroNode temp head;//遍历链表找到最后while (true) {//找到链表最后if(temp.next null){break;}//如果没有找到 最后将temp后移temp temp.next;}//当退出while循环时temp就指向了链表的最后//将最后这个节点的next 指向 新的节点temp.next heroNode;}//第二种方式在添加英雄时根据排名将英雄插入到指定位置//如果有这个排名则添加失败并给出提示public void addByOrder(HeroNode heroNode){//因为头节点不能动因此我们仍然通过一个辅助指针变量来帮助找到添加的位置//因为单列表我们找的temp是位于添加位置的前一个节点否则插入不了HeroNode temp head;boolean flag false;//标识添加的编号是否已经存在默认为falsewhile (true) {if(temp.next null){//说明temp已经在链表的最后break;}if(temp.next.no heroNode.no){//位置找到就在temp的后面插入break;}else if (temp.next.no heroNode.no) {//说明希望添加的heroNode的编号已经存在flag true;//说明编号存在break;}temp temp.next;//后移遍历当前链表}//判断flag的值if (flag) {//不能添加说明编号存在System.out.printf(准备插入的英雄编号 %d 已经存在了不能添加\n, heroNode.no);}else{//插入到链表中temp的后面heroNode.next temp.next;temp.next heroNode;}}//修改节点的信息, 根据 no 编号来修改即 no 编号不能改. //说明//1. 根据 newHeroNode 的 no 来修改即可public void update(HeroNode newHeroNode) {//判断是否空if(head.next null) {System.out.println(链表为空~);return;}//找到需要修改的节点, 根据 no 编号//定义一个辅助变量HeroNode temp head.next;boolean flag false; //表示是否找到该节点while(true) {if (temp null) {break; //已经遍历完链表}if(temp.no newHeroNode.no) {//找到flag true;break;}temp temp.next;}//根据 flag 判断是否找到要修改的节点if(flag) {temp.name newHeroNode.name;temp.nickname newHeroNode.nickname;} else { //没有找到System.out.printf(没有找到 编号 %d 的节点不能修改\n, newHeroNode.no);}}//删除节点//思路//1. head 不能动因此我们需要一个temp辅助节点找到待删除节点的前一个节//2. 说明我们在比较时是temp.next.no 和 需要删除的节点的no比较public void del(int no){HeroNode temp head;boolean flag false;//标识是否找到待删除的节点while(true){if(temp.next null){//已经到链表的最后break;}if(temp.next.no no){//找到的待刪除节点的前一个节点tempflag true;break;}temp temp.next;//temp后移}//判断flagif(flag){//找到//可以删除temp.next temp.next.next;}else{System.out.printf(要删除的 %d 节点不存在\n, no);}}//显示链表[遍历]public void list(){//先判断链表是否为空if(head.next null){System.out.println(链表为空);return;}//因为头节点不能动每个HeroNode对象就是一个节点HeroNode temp head.next;while (true) {//判断是否到链表最后if(temp null){break;}//输出节点的信息System.out.println(temp);//将next后移。不后移就成了死循环一定小心temp temp.next; }}
}//定义一个 HeroNode每个 HeroNode 对象就是一个节点
class HeroNode{public int no;public String name;public String nickname;public HeroNode next;//指向下一个节点//构造器public HeroNode(int No, String Name, String Nickname){this.no No;this.name Name;this.nickname Nickname;}//为了显示方便我们重写toStringOverridepublic String toString() {// return HeroNode [no no , name name , nickname nickname , next next ];return HeroNode [no no , name name , nickname nickname ];}
}运行结果 5.4. 从尾到头打印单链表
百度面试题 做这道题之前先学习栈
代码示例
package Linkedlist;import java.util.Stack;//stack的基本使用
public class TestStack {public static void main(String[] args){StackString stack new Stack();//入栈stack.add(jack);stack.add(tom);stack.add(smith);//出栈顺序smith,tom,jackwhile (stack.size() 0) {System.out.println(stack.pop());//pop就是将栈顶的数据取出}}}运行结果 思路分析 思路 上面的题的要求就是逆序打印单链表. 方式1 先将单链表进行反转操作然后再遍历即可这样的做的问题是会破坏原来的单链表的结构不建议 方式2可以利用栈这个数据结构将各个节点压入到栈中然后利用栈的先进后出的特点就实现了逆序打印的效果。 功能实现
//逆序打印单链表//方式2可以利用栈这个数据结构将各个节点压入到栈中然后利用栈的先进后出的特点就实现了逆序打印的效果.public static void reversePrint(HeroNode head){if (head.next null) {return;//空链表不能打印}//创建一个栈将节点压入栈中StackHeroNode stack new StackHeroNode();HeroNode cur head.next;//将链表的所有节点压入栈while(cur ! null) {stack.push(cur);cur cur.next;}//将栈中的节点进行打印。pop出栈while (stack.size() 0) {System.out.println(stack.pop());}}完整代码实现
package Linkedlist;import java.net.http.HttpHeaders;
import java.util.Stack;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.addByOrder(hero1);singleLinkedList.addByOrder(hero4);singleLinkedList.addByOrder(hero2);singleLinkedList.addByOrder(hero3);// singleLinkedList.addByOrder(hero3);//显示链表singleLinkedList.list();System.out.println(-----------逆序打印没有改变链表的结构--------------);reversePrint(singleLinkedList.getHead());}//逆序打印单链表//方式2可以利用栈这个数据结构将各个节点压入到栈中然后利用栈的先进后出的特点就实现了逆序打印的效果.public static void reversePrint(HeroNode head){if (head.next null) {return;//空链表不能打印}//创建一个栈将节点压入栈中StackHeroNode stack new StackHeroNode();HeroNode cur head.next;//将链表的所有节点压入栈while(cur ! null) {stack.push(cur);cur cur.next;}//将栈中的节点进行打印。pop出栈while (stack.size() 0) {System.out.println(stack.pop());}}//将单链表反转public static void reversetList(HeroNode head){//如果当前链表为空或者只有一个节点无需反转直接返回if(head.next null || head.next.next null){return;}//定义一个辅助的指针变量帮助我们遍历原来的链表HeroNode cur head.next;HeroNode next null;//指向当前节点[cur]的下一个节点HeroNode reverseHead new HeroNode(0, , );//遍历原来的链表每遍历一个节点就将其取出并放在新的链表reverseHead 的最前端while (cur ! null) {next cur.next;//先暂时保存当前节点的下一个节点后面需要使用cur.next reverseHead.next;//将cur的下一个节点指向新的链表的最前端reverseHead.next cur;cur next;//让cur后移}//将head.next 指向reverseHead.next实现单链表的反转head.next reverseHead.next;}//查找单链表中的倒数第k个节点【新浪面试题】//思路//1. 编写一个方法接收head节点同时接收一个index//2. index 表示是倒数第index个节点//3. 先把链表从头到尾遍历得到链表的总长度getLength//4. 得到size(getLength)后我们从链表的第一个开始遍历size-index个就可以得到//5. 如果找到了则返回该节点否则返回nullpublic static HeroNode findLastIndexNode(HeroNode head, int index){//判断如果链表为空返回nullif(head.next null){return null;//没有找到}//第一次遍历得到链表的长度节点个数int size getLength(head);//第二次遍历 size-index 位置//先做一个index的校验if(index 0 || index size){return null;}//定义一个辅助变量,for循环定位到倒数的indexHeroNode cur head.next;//假设链表有3个数据查找倒数第一个数据那么size-index3-12for(int i 0; i size - index; i){cur cur.next;}return cur;}//方法获取单链表的节点个数如果是带头节点的链表那么久不统计头节点/*** * param head* return*/public static int getLength(HeroNode head){if(head.next null){//空链表return 0;}int length 0;//定义一个辅助变量,没有统计头节点HeroNode cur head.next;while(cur ! null) {length;cur cur.next;//遍历}return length;}
}//定义SingleLinkedList 管理我们的英雄人物
class SingleLinkedList{//先初始化一个头节点头节点不要动,不存放具体的数据private HeroNode head new HeroNode(0, null, null);//返回头节点public HeroNode getHead() {return head;}//添加节点到单向链表//思路当不考虑编号顺序时//1. 找到当前链表的最后节点//2. 将最后这个节点的next指向新的节点public void add (HeroNode heroNode){//因为head节点不能动因此我们需要一个辅助遍历tempHeroNode temp head;//遍历链表找到最后while (true) {//找到链表最后if(temp.next null){break;}//如果没有找到 最后将temp后移temp temp.next;}//当退出while循环时temp就指向了链表的最后//将最后这个节点的next 指向 新的节点temp.next heroNode;}//第二种方式在添加英雄时根据排名将英雄插入到指定位置//如果有这个排名则添加失败并给出提示public void addByOrder(HeroNode heroNode){//因为头节点不能动因此我们仍然通过一个辅助指针变量来帮助找到添加的位置//因为单列表我们找的temp是位于添加位置的前一个节点否则插入不了HeroNode temp head;boolean flag false;//标识添加的编号是否已经存在默认为falsewhile (true) {if(temp.next null){//说明temp已经在链表的最后break;}if(temp.next.no heroNode.no){//位置找到就在temp的后面插入break;}else if (temp.next.no heroNode.no) {//说明希望添加的heroNode的编号已经存在flag true;//说明编号存在break;}temp temp.next;//后移遍历当前链表}//判断flag的值if (flag) {//不能添加说明编号存在System.out.printf(准备插入的英雄编号 %d 已经存在了不能添加\n, heroNode.no);}else{//插入到链表中temp的后面heroNode.next temp.next;temp.next heroNode;}}//修改节点的信息, 根据 no 编号来修改即 no 编号不能改. //说明//1. 根据 newHeroNode 的 no 来修改即可public void update(HeroNode newHeroNode) {//判断是否空if(head.next null) {System.out.println(链表为空~);return;}//找到需要修改的节点, 根据 no 编号//定义一个辅助变量HeroNode temp head.next;boolean flag false; //表示是否找到该节点while(true) {if (temp null) {break; //已经遍历完链表}if(temp.no newHeroNode.no) {//找到flag true;break;}temp temp.next;}//根据 flag 判断是否找到要修改的节点if(flag) {temp.name newHeroNode.name;temp.nickname newHeroNode.nickname;} else { //没有找到System.out.printf(没有找到 编号 %d 的节点不能修改\n, newHeroNode.no);}}//删除节点//思路//1. head 不能动因此我们需要一个temp辅助节点找到待删除节点的前一个节//2. 说明我们在比较时是temp.next.no 和 需要删除的节点的no比较public void del(int no){HeroNode temp head;boolean flag false;//标识是否找到待删除的节点while(true){if(temp.next null){//已经到链表的最后break;}if(temp.next.no no){//找到的待刪除节点的前一个节点tempflag true;break;}temp temp.next;//temp后移}//判断flagif(flag){//找到//可以删除temp.next temp.next.next;}else{System.out.printf(要删除的 %d 节点不存在\n, no);}}//显示链表[遍历]public void list(){//先判断链表是否为空if(head.next null){System.out.println(链表为空);return;}//因为头节点不能动每个HeroNode对象就是一个节点HeroNode temp head.next;while (true) {//判断是否到链表最后if(temp null){break;}//输出节点的信息System.out.println(temp);//将next后移。不后移就成了死循环一定小心temp temp.next; }}
}//定义一个 HeroNode每个 HeroNode 对象就是一个节点
class HeroNode{public int no;public String name;public String nickname;public HeroNode next;//指向下一个节点//构造器public HeroNode(int No, String Name, String Nickname){this.no No;this.name Name;this.nickname Nickname;}//为了显示方便我们重写toStringOverridepublic String toString() {// return HeroNode [no no , name name , nickname nickname , next next ];return HeroNode [no no , name name , nickname nickname ];}
}运行结果
