链表
-
链表是以节点的方式进行存储的。
-
每个节点包含：data域 和 next域：指向下一个节点。
-
链表的各个节点不一定是连续存储的。
-
链表分为带头结点的和不带头节点的。
Node 节点
public class HeroNode {
private int no; // 编号
private String name; //名字
private String nickname; // 外号
private HeroNode next; //下一个节点
public HeroNode(int no, String name, String nickname) {
this.no = no;
this.name = name;
this.nickname = nickname;
}
@Override
public String toString() {
return "HeroNode{" +
"no=" + no +
", name='" + name + '\'' +
", nickname='" + nickname + '\'' +
'}';
}
public void setNo(int no) {
this.no = no;
}
public void setName(String name) {
this.name = name;
}
public void setNickname(String nickname) {
this.nickname = nickname;
}
public void setNext(HeroNode next) {
this.next = next;
}
public int getNo() {
return no;
}
public String getName() {
return name;
}
public String getNickname() {
return nickname;
}
public HeroNode getNext() {
return next;
}
}
SingleLinkedList 单链表
public class SingleLinkedList {
//创建头节点
public HeroNode head = new HeroNode(0,"","");
// 打印节点
public void showLinked(){
// 判断链表是否为空
if (head.getNext()==null){
System.out.println("链表为空");
return;
}
// 链表不为空循环遍历打印输出
HeroNode temp = head.getNext();
while (true){
//判断是否为尾节点
if (temp==null) {
break;
}
//不是则打印下一个节点
System.out.println(temp);
//指针后移
temp = temp.getNext();
}
}
// 添加节点
public void addNode(HeroNode heroNode){
//先找到尾部节点再进行插入
//创建一个temp指针进行遍历,这里我就直接让temp指向头结点的下一个节点
HeroNode temp = head;
while (true){
//判断节点是否为空
if (temp.getNext()==null){
break;
}
//不是尾节点指针后移
temp = temp.getNext();
}
//经过遍历temp就是尾部节点
temp.setNext(heroNode);
}
/**
* 按照编号添加节点
*/
public void addByOrder(HeroNode heroNode){
//由于是单链表temp只能在插入节点之前！！！
HeroNode temp = head;
boolean flag = false;//判断插入的编号是否存在
while (true){
// 查看是不是最后一个节点
if (temp.getNext()==null){break;}
// 查看插入的位置
if (temp.getNext().getNo()>heroNode.getNo()){
//位置找到就应该在temp的后面添加
break;
}else if(temp.getNext().getNo() == heroNode.getNo()){
//说明编号已经存在
flag = true;
break;
}
temp = temp.getNext();
}
if (flag){
//不能插入文字提示
System.out.printf("待插入的英雄（编号：%d）已经存在\n",heroNode.getNo());
}else {//插入内容
heroNode.setNext(temp.getNext());
temp.setNext(heroNode);
}
}
/**
* 根据no来修改节点信息,即no 不能发生改变
*/
public void update(HeroNode heroNode){
//判断练表是否为空
if (head.getNext()==null){
System.out.println("链表为空");
return;
}
HeroNode temp = head.getNext();
boolean flag = false; //判断链表是否找到这个节点
while (true){
//判断链表是否为空
if (temp == null){
break;
}
// 判断链表是否找到这个节点
if (temp.getNo()==heroNode.getNo()){
flag=true;
break;
}
temp = temp.getNext();
}
//判断链表是否找到这个节点
if (flag){
temp.setName(heroNode.getName());
temp.setNickname(heroNode.getNickname());
}else {
System.out.println("链表不存在此节点:"+heroNode);
}
}
/**
* 根据no删除节点
* temp.next = temp.next.next
* 未被引用的节点会被JVM的垃圾回收机制回收
*/
public void delete(int no){
HeroNode temp = head;
//是否找到删除节点
boolean flag = false;
while (true){
//判断链表是否为空
if (temp.getNext()==null){
break;
}
if (temp.getNext().getNo()==no){
//找到节点
flag = true;
break;
}
temp = temp.getNext();//指针后移，继续遍历
}
if (flag){
temp.setNext(temp.getNext().getNext());
}else {
System.out.println("删除====该节点值不存在");
}
}
}
链表的面试题
- 求单链表中有效节点的个数。
- 查找单链表中的倒数第K个结点。==新浪面试题==
- 链表的反转。==腾讯面试题==
- 从尾到头打印单链表。==百度== 方式1：反向遍历2：Stack栈
- 合并两个有序的单链表，合并之后的链表仍然有序。（课后练习）
1.求单链表中有效节点的个数。
//题目1：方法：取到单链表的节点个数（不计入头节点）
/**
* @param head 链表的头节点
* @return 返回有效节点个数
*/
public static int getLength(HeroNode head){
if (head.getNext()==null){//空链表
return 0;
}
int length = 0;
HeroNode temp = head.getNext();
while (temp!=null){
length++;
temp = temp.getNext();
}
return length;
}
- 查找单链表中的倒数第K个结点。==新浪面试题==
//题目2：查找单链表中的倒数第K个结点
//思路：将倒数变成正数
public HeroNode findLastIndexNode(HeroNode head,int index){
if (head.getNext()==null){//空链表
return null;
}
//第一次遍历获取链表长度
int length = getLength(head);
//第二次遍历寻找值
//判断index是否合法
if (index < 0 || index >length){
return null;
}
HeroNode cur = head.getNext();
// 遍历寻找
for (int i = 0; i < length - index; i++) {
cur = cur.getNext();
}
return cur;
}
- 链表的反转。==腾讯面试题==
public void reverseList(HeroNode head){
//判断如果链表为空或者链表只有一个节点则不需要操作
if (head.getNext()==null || head.getNext().getNext()==null){
return;
}
//定义辅助遍历来帮助我们遍历链表
HeroNode cur = head.getNext();
HeroNode next = null;// 指向cur下一个节点
HeroNode reverseHead = new HeroNode(0,"","");
//遍历原来的链表，没遍历一个节点就将其放到reverseHead的最前端
while (cur!=null){
next = cur.getNext(); //next 来保存遍历的位置
cur.setNext(reverseHead.getNext());
reverseHead.setNext(cur);
cur = next;
}
head.setNext(reverseHead.getNext());
}
- 题目4：从尾到头打印单链表
//题目4：从尾到头打印单链表
// 方法：
// 1. 反转链表 会改变原有数据的结构，并且操作复杂度高，不推荐
// 2. stack栈的方式 适用栈的特点：先进后出 将数据压入栈中 再取出数据就会反过来
public void reversePrint(HeroNode head){
if (head.getNext()==null){//判断链表是否为空
return;
}
HeroNode cur = head.getNext();//设置辅助指针
Stack<HeroNode> stack = new Stack<>();// 使用栈
while (cur!=null){
stack.push(cur);
cur = cur.getNext();
}
while (stack.size()>0){
System.out.println(stack.pop());
}
}
网友评论