【Java数据结构与算法】第二章单链表及简单面试题

第二章单链表

文章目录

第二章单链表一、单链表1.基本介绍2.思路3.代码实现二、简单面试题1.求单链表中有效节点的个数2.查找单链表中的倒数第k个节点（新浪面试题）3.单链表的反转（腾讯面试题）4.逆序打印单链表（百度面试题）

一、单链表

1.基本介绍

链表是有序的列表，他在内存中如下存储

单链表（带头节点）的逻辑结构如下

链表是以节点的方式来存储的，是链式存储每个节点包含 data 域， next 域（指向下一个节点）链表的各个节点不一定是连续存储链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定

2.思路

创建：

创建一个 head 头节点，作用是表示单链表的头每添加一个节点，就直接加入到链表的最后

遍历：

借助temp辅助变量（指针），遍历整个链表

添加：

借助temp辅助变量，通过遍历来找到新节点要加入的位置新节点.next = tem.nexttemp.next = 新节点

删除：

找到需要删除的节点的前一个节点 temptemp.next = temp.next.next被删除的节点由于没有其它引用指向，会被垃圾回收机制回收

3.代码实现

使用带头节点的单向链表实现水浒英雄排行榜管理，要求能完成对英雄人物的增删改查

package com.sisyphus.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.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.queryByName("小卢");//删除一个节点singleLinkedList.del(1);singleLinkedList.del(3);singleLinkedList.del(4);System.out.println("删除后的链表情况：");singleLinkedList.list();}}//定义SingleLinkedList 管理我们的英雄class SingleLinkedList{//先初始化一个头节点，头节点不能动，否则会找不到这个链表private HeroNode head = new HeroNode(0,"","");//添加节点到单向链表//当不考虑编号顺序时：//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){//因为头节点不能动，因此我们仍借助辅助变量来找到添加的位置//我们要找位于添加位置的前一个节点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){//说明编号存在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;}}//修改节点的信息，根据编号来修改，即编号不能修改//说明//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 的节点",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; //后移继续遍历}//判断flagif (flag){//找到//可以删除temp.next = temp.next.next;}else{System.out.printf("要删除的 %d 节点不存在\n",no);}}//展示链表//借助temp辅助变量，遍历整个链表public void list(){//判断链表是否为空if(head.next == null){System.out.println("链表为空");return;}//因为头节点不能动，因此我们需要一个辅助变量来遍历HeroNode temp = head.next;while(true){//判断是否在链表的尾部if (temp == null){break;}//输出节点信息System.out.println(temp);//将 temp 后移temp = temp.next;}}//根据名称查询链表public void queryByName(String name){//判断链表是否为空if(head.next == null){System.out.println("链表为空");return;}HeroNode temp = head.next;boolean flag = true; //表示是否找到对应节点while (true){//判断是否在链表的尾部if (temp == null){break;}if (temp.name == name){flag = false;System.out.println("查询成功：");System.out.println(temp);break;}temp = temp.next;}if (flag){System.out.println("链表中没有对应节点！");}}}//定义 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;}//为了显示方法，我们重新 toString@Overridepublic String toString() {return "HeroNode{" +"no=" + no +", name='" + name + '\'' +", nickname='" + nickname + '\'' +'}';}}