- 节点，next指向下一个节点
class Node {
public int id;
public String name;
public Node next;
public Node(int id, String name) {
this.id = id;
this.name = name;
}
}
复制代码
- 通过链表对象实现，管理node
class SinglelinkedList {
//初始化头节点，头节点不能动，不存放数据
private Node head = new Node(0,"");
//增删改查方法…
}
复制代码
- 添加，不考虑编号顺序，找到当前链表的最后节点，将最后这个节点的next指向新节点，通过temp.next == null来判断，是否为最后一个节点
public void add(Node node) {
//头节点不能动，通过辅助节点进行遍历
Node temp = head;
while (true) {
//最后一个节点的next指向空
if (temp.next == null) {
break;
}
//如果没有找到最后，就将temp后移
temp = temp.next;
}
//当退出while循环，temp指向链表的最后
temp.next = node;
}
复制代码
- 按照顺序添加，断开要插入位置的前一个节点与后一个节点的连接，并将后一个节点连接上要插入的节点；node.next = temp.next;；再连接前一个节点与要插入的节点temp.next = node;
public void addByOrder(Node node) {
//通过辅助变量找到插入的位置，位于添加位置的前一个节点
Node temp = head;
boolean flag = false; //添加的编号是否已经存在，默认为false
while (true) {
//说明temp已经在最后了
if (temp.next == null) {
break;
}
//找到位置，这个位置的后一个id要大于要添加的id
if (temp.next.id > node.id) {
break;
} else if (temp.next.id == node.id) {
//添加的id已经存在，不能添加
flag = true;
break;
}
//后移
temp = temp.next;
}
if (flag) {
System.out.println(“准备插入的节点已经存在，修改名字”);
temp.next.name = node.name;
} else {
//插入到链表中 例如 1 3，2要插入，1是temp，2的下一个节点指向3，1的下一个节点指向2
//要插入的节点的下一个节点指向temp的下一个节点
node.next =
【一线大厂Java面试题解析+后端开发学习笔记+最新架构讲解视频+实战项目源码讲义】 浏览器打开：qq.cn.hn/FTf 免费领取
temp.next;
//找到的位置要指向要插入的节点
temp.next = node;
}
}
复制代码
- 修改，根据id修改，id不能改变
public void update(Node node) {
if (head.next == null) {
System.out.println(“List is empty”);
return;
}
Node temp = head;
boolean flag = false; //是否找到该节点
while (true) {
if (temp == null) {
break;
}
if (temp.id == node.id) {
//找到节点
flag = true;
break;
}
temp = temp.next;
}
if (flag) {
temp.name = node.name;
} else {
System.out.println(“node - " + node.id + " does not exist.”);
}
}
复制代码
- 删除，head不能动，通过temp找到要删除的节点的前一个节点；待删除的节点的前一个节点temp的下一个节点，指向待删除节点temp.next的下一个节点temp.next.next
public void del(int id) {
Node temp = head;
boolean flag = false; //是否找到待删除的节点
while (true) {
//已经到了链表的最后且没有找到
if (temp.next == null) {
break;
}
if (temp.next.id == id) {
//找到待删除的节点的前一个节点
flag = true;
break;
}
temp = temp.next;
}
if (flag) {
temp.next = temp.next.next;
} else {
System.out.println(“没有找到id为” + id + “的节点”);
}
}
复制代码
- 显示
public void list() {
//判断链表是否为空
if (head.next == null) {
System.out.println(“List is empty”);
return;
}
//通过辅助变量，进行遍历，从头节点的后一个开始遍历
Node temp = head.next;
while (true) {
//判断是否到链表最后
if (temp == null) {
break;
}
System.out.println(temp);
//后移节点
temp = temp.next;
}
}
复制代码
单链表面试题- 求单链表中有效节点的个数
//获取单链表节点个数，如果带头节点的链表，不统计头节点
public static int getLength(Node head) {
if (head.next == null) {
//空链表
return 0;
}
int length = 0;
Node cur = head.next;
while (cur != null) {
length ++;
cur = cur.next;
}
return length;
}
复制代码
- 查找倒数第K个节点，假设长度为3，查找倒数第2个，也就是正数第二个，cur需要从头head.next移动1次，也就是正数移动size-index
public static Node findLastIndexNode(Node head, int index) {
if (head.next == null) { //空
return null;
}
//得到链表长度
int size = getLength(head);
//第二次遍历获取目标
