JAVA- 数据结构与算法，mysql 数据库应用与实践教程
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 = 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);
//第二次遍历获取目标
if (index <= 0 || index > size) {
return null;
}
Node cur = head.next;
for (int i = 0; i < size - index; i++) {
cur = cur.next;
}
return cur;
}
复制代码
单链表反转，当前
cur.next指向reverseHead.next，reverseHead.next指向cur，使cur插入reverseHead与reverseHead.next之间；从头到尾遍历原链表，就可以把后面的不断提前；next保存原链表中的下一个，等cur操作完成后进行替换
public static void reverseLinkedList(Node head) {
if (head.next == null || head.next.next == null) {
return;
}
Node cur = head.next;
//指向当前节点的下一个节点
Node next = null; //cur 的下一个节点
Node reverseHead = new Node(0,"");
//遍历原来的列表
while (cur != null) {
next = cur.next; //保存当前节点的下一个节点
cur.next = reverseHead.next; //将 cur 下一个节点指向新的列表的头部
reverseHead.next = cur;
cur = next;
}
//将 head.next 指向 reverseHead.next;
head.next = reverseHead.next;
}
复制代码
从尾到头打印单链表，利用栈(先进后出)实现逆序打印
public static void reversePrint(Node head) {
if (head.next == null) {
return;
}
//创建栈
Stack<Node> nodes = new Stack<>();
Node cur = head.next;
while (cur != null) {
nodes.push(cur);
cur = cur.next;
}
while (nodes.size() > 0) {
System.out.println(nodes.pop());
}
还未添加个人签名 2021.03.18 加入
还未添加个人简介
评论