1.单链表

1.基本介绍

1.定义

2.逻辑结构

2.应用实例

1.需求分析

2.思路分析

3.完成添加和显示链表信息，直接添加到链表的尾部

package com.sun.linkedlist;import java.util.Scanner;/*** @author 孙显圣* @version 1.0*/class Test {public static void main(String[] args) {SingleLinkedList singleLinkedList = new SingleLinkedList();//添加几条记录Node node1 = new Node(1, "李白", "青莲剑歌");Node node2 = new Node(2, "杜甫", "青莲剑歌");Node node3 = new Node(3, "周瑜", "青莲剑歌");Node node4 = new Node(4, "诸葛亮", "青莲剑歌");singleLinkedList.add(node2);singleLinkedList.add(node1);singleLinkedList.add(node4);singleLinkedList.add(node3);boolean flag = true;while (flag) {System.out.println("1：显示，2：入队，3：出队，4：退出");Scanner scanner = new Scanner(System.in);int cmd = scanner.nextInt();switch (cmd) {case 1:singleLinkedList.list();break;case 2:System.out.println("请输入要添加的数据：");System.out.println("编号：");int no = scanner.nextInt();System.out.println("姓名：");String name = scanner.next();System.out.println("技能");String skill = scanner.next();Node node = new Node(no, name, skill);singleLinkedList.add(node);System.out.println("添加成功！");break;case 3:break;case 4:flag = false;System.out.println("退出系统");}}}
}//用来管理节点
public class SingleLinkedList {//头结点，指向第一个元素private Node head = new Node();//添加节点public void add(Node node) {//遍历链表直到最后，然后添加节点//由于头结点不能动，所以需要一个辅助节点来遍历Node temp = head;while (true) {//只要临时节点的下一个节点不为空，就将临时节点向后移动if (temp.next != null) {//节点向后移动temp = temp.next;continue;}//当临时节点的下一个节点为空，则添加一个数据，然后退出循环temp.next = node;break;}}//遍历链表，显示信息public void list() {//临时节点指向头结点Node temp = head;while (temp.next != null) {//显示节点信息System.out.println(temp.next);temp = temp.next;}}}//编写一个节点类型，每一个对象即为一个节点
class Node {//数据域public int no;public String name;public String skill;//next域，指向下一个节点public Node next;public Node() {}public Node(int no, String name, String skill) {this.no = no;this.name = name;this.skill = skill;}@Overridepublic String toString() {return "Node{" +"no=" + no +", name='" + name + '\'' +", skill='" + skill + '\'' +'}';}
}

4.根据排名添加，如果排名重复则给出提示

    //按照顺序添加节点public void addBySequential(Node node) {//辅助节点Node temp = head;//遍历节点//只要下一个数不等于空并并且下一个数比当前数要小，则一定不是要插入的位置，所以向后移动while (temp.next != null && temp.next.no <= node.no) {temp = temp.next;}//只要出了循环就表示，下一个数是空或者下一个数大于当前的数，可以插入node.next = temp.next;temp.next = node;}

5.根据新节点的编号来修改信息

    //根据新节点的信息来修改链表public void update(Node newNode) {//根据id来查找到链表的那个节点//临时节点指向头结点Node temp = head;//只要下一个元素不为空就进入循环while (temp.next != null) {//如果符合条件，就修改这个节点的值if (temp.next.no == newNode.no) {//修改节点的值temp.next.name = newNode.name;temp.next.skill = newNode.skill;System.out.println("修改成功！修改后的节点信息为：" + temp.next);break;}//只要不符合条件就一直走temp = temp.next;}}

6.删除指定id的节点

    //删除指定id的节点public void del(int no) {//找到指定编号的节点的前一个位置Node temp = head;//只要没有找到指定no的节点就往后走while (temp.next != null) {if (temp.next.no == no) {//删除temp的下一个节点temp.next = temp.next.next;System.out.println("节点" + no + "删除成功！");break;}temp = temp.next;}}

3.单链表面试题

1.题目

2.面试题一

    // 1.根据头结点求单链表中有效节点的个数public int getLength(Node head) {// 根据头结点遍历即可// 临时节点Node temp = head;int length = 0; // 初始化长度为0// 只要临时节点的下一个节点不为空，则说明有一个有效节点，所以长度++while (temp.next != null) {length++;temp = temp.next;}return length;}

2.面试题二

    // 2.查找单链表的倒数第几个节点public Node numberOfCollapses(Node head, int tail) {// 得到有效节点的数量int length = getLength(head);if (tail > length) {throw new RuntimeException("输入有误！");}// 计算是正数第几个节点int index = length - tail + 1;// 遍历得到正数第index个节点Node temp = head;int temp_index = 0; // 记录是第几个节点while (temp.next != null) {temp_index++;if (temp_index == index) {return temp.next;}temp = temp.next;}return null;}

3.面试题三

    // 3.单链表反转public void linkedListInversion(Node head) {// 排除零个节点和一个节点的情况if (head.next == null || head.next.next == null) {return;}// 临时指针一Node temp1 = head.next;// 临时指针二Node temp2 = new Node();// 反转链表的一个临时节点Node reverseHead = new Node();// 使用双指针遍历单链表while (temp1 != null) {// 让第二个指针指向第一个指针的后面if (temp1.next != null) {temp2 = temp1.next;} else {// 如果第一个指针的下一个位置为空，则让第二个指针指向null，这样移动完一个节点之后第一个指针就会指向第二个指针也就是空，可以退出循环temp2 = null;}// 将temp1指向的节点接入到reverseHead后面temp1.next = reverseHead.next;reverseHead.next = temp1;// 利用第二个指针移动temp1temp1 = temp2;}// 反转成功之后让head节点指向第一个节点head.next = reverseHead.next;}

4.面试题四

    // 4，从尾到头打印单链表public void reversePrint(Node head) {// 只要链表没有元素就直接returnif (head.next == null) {return;}// 创建一个栈Stack<Node> stack = new Stack<>();// 将各个节点依次压入栈中Node temp = head.next;while (temp != null) {stack.push(temp);temp = temp.next;}// 取出栈中的元素while (stack.size() > 0) {System.out.println(stack.pop());}}

2.双向链表

1.增删改查分析图解

2.代码实现

package com.sun.linkedlist;/*** Description: 双向链表** @Author sun* @Create 2024/3/28 20:53* @Version 1.0*/
// 双向链表方法的测试
class DoubleLinkedListDemoTest {public static void main(String[] args) {// 创建一个双向链表DoubleLinkedListDemo doubleLinkedListDemo = new DoubleLinkedListDemo();// 创建几个节点Node2 node1 = new Node2(1, "李白", "青莲剑歌");Node2 node2 = new Node2(2, "杜甫", "青莲剑歌");Node2 node3 = new Node2(3, "周瑜", "青莲剑歌");Node2 node4 = new Node2(4, "诸葛亮", "青莲剑歌");// 添加节点doubleLinkedListDemo.add(node1);doubleLinkedListDemo.add(node2);doubleLinkedListDemo.add(node3);doubleLinkedListDemo.add(node4);// 遍历doubleLinkedListDemo.list();// 修改节点Node2 updateNode = new Node2(4, "4", "4");doubleLinkedListDemo.update(updateNode);// 删除节点doubleLinkedListDemo.del(4);// 遍历doubleLinkedListDemo.list();System.out.println("====================================");// 把编号打乱，测试按照编号添加的方法Node2 node5 = new Node2(5, "5", "5");Node2 node6 = new Node2(6, "6", "6");Node2 node7 = new Node2(7, "7", "7");Node2 node8 = new Node2(8, "8", "8");// 从node8逆序添加doubleLinkedListDemo.insertByOrder(node8);doubleLinkedListDemo.insertByOrder(node7);doubleLinkedListDemo.insertByOrder(node6);doubleLinkedListDemo.insertByOrder(node5);// 遍历doubleLinkedListDemo.list();}
}public class DoubleLinkedListDemo {// 初始化双向链表// 头结点，指向第一个元素private Node2 head = new Node2(-1, "", "");public Node2 getHead() {return head;}// 遍历的方法与单向链表相同public void list() {// 判断链表是否为空if (head.next == null) {System.out.println("链表为空");return;}// 临时节点Node2 temp = head.next;// 只要临时节点不为空，就输出当前节点信息，然后向后移动while (temp != null) {System.out.println(temp);temp = temp.next;}}// 添加节点public void add(Node2 node2) {// 临时节点Node2 temp = head;// 首先遍历找到最后一个节点while (temp.next != null) {temp = temp.next;}// 目前temp 指向了最后一个节点temp.next = node2;node2.pre = temp;}// 修改节点，跟单向链表一致public void update(Node2 newNode) {// 根据id来查找到链表的那个节点// 临时节点指向头结点Node2 temp = head;// 只要下一个元素不为空就进入循环while (temp.next != null) {// 如果符合条件，就修改这个节点的值if (temp.next.no == newNode.no) {// 修改节点的值temp.next.name = newNode.name;temp.next.skill = newNode.skill;System.out.println("修改成功！修改后的节点信息为：" + temp.next);break;}// 只要不符合条件就一直走temp = temp.next;}}// 从双向链表中删除节点，首先找到要删除的节点，然后自我删除即可// 删除指定id的节点public void del(int no) {// 首先判断链表是否为空if (head.next == null) {System.out.println("链表为空，不能删除");return;}// 临时节点指向第一个节点（这是因为第一个节点不为空才能这样）Node2 temp = head.next;// 只要没有找到指定no的节点就往后走while (temp != null) {// 判断是否是要找的节点if (temp.no == no) {// 执行自我删除temp.pre.next = temp.next;if (temp.next != null) {// 这里如果temp指向了最后一个元素，则不执行，否则会报temp.next.pre = temp.pre;}System.out.println("节点" + no + "删除成功！");break;}// 后移temp = temp.next;}}// 按照编号顺序来添加public void insertByOrder(Node2 newNode) {// 临时节点Node2 temp = head;// 只要临时节点的下一个节点不为空，并且no比新节点要小，就继续走while (temp.next != null && temp.next.no < newNode.no) {temp = temp.next;}// 目前停下来只有两种情况，一种是temp.next == null, 另一种是temp.next >= newNode.no// 如果下一个元素为空，则直接插入到temp的后面if (temp.next == null) {temp.next = newNode;newNode.pre = temp;return;}// 剩下的情况就是下一个元素不为空，则插入到temp跟下一个元素之间// 先插后面temp.next.pre = newNode;newNode.next = temp.next;// 再插前面temp.next = newNode;newNode.pre = temp;}}// 编写一个节点类型，每一个对象即为一个节点
class Node2 {// 数据域public int no;public String name;public String skill;// next域，指向下一个节点public Node2 next;public Node2 pre;public Node2() {}public Node2(int no, String name, String skill) {this.no = no;this.name = name;this.skill = skill;}@Overridepublic String toString() {return "Node{" +"no=" + no +", name='" + name + '\'' +", skill='" + skill + '\'' +'}';}
}

3.单向环形链表

1.题目

2.思路分析

3.首先构建一个环形链表

1.思路分析

2.代码

package com.sun.linkedlist;/*** Description:** @Author sun* @Create 2024/3/29 21:39* @Version 1.0*/
public class Josephu {private Boy first = null;public static void main(String[] args) {Josephu josephu = new Josephu();josephu.addBoy(3);josephu.show();}/*** 根据数量添加小孩* @param nums*/public void addBoy(int nums) {// 数据校验if (nums < 1) {System.out.println("输入数据有误！");return;}// 对第一个数据做出特殊处理Boy boy1 = new Boy(1);first = boy1;first.setNext(first);Boy curBoy = first;// 后续的数据循环处理for (int i = 2; i <= nums; i++) {Boy boy = new Boy(i);curBoy.setNext(boy);boy.setNext(first);curBoy = boy;}}// 遍历public void show() {Boy temp = first;while (true) {System.out.print(temp.getNo() + " ");if (temp.getNext() == first) {return;} else {temp = temp.getNext();}}}
}// 创建节点对象
class Boy {private int no;private Boy next;public Boy(int no) {this.no = no;}public Boy getNext() {return next;}public void setNext(Boy next) {this.next = next;}public int getNo() {return no;}
}

4.具体问题解决

1.思路分析

2.代码

    // 数小孩/**** @param ranking 从第几个开始数* @param count 数几个* @param total 一共有几个小孩*/public void countChild(int ranking, int count, int total) {// 进行简单校验if (ranking < 1 || ranking > total) {System.out.println("输入数据有误");return;}// 首先构建小孩addBoy(total);// 辅助指针helper指向最后一个元素Boy helper = first;while (true) {if (helper.getNext() == first) {break;}// 向后移动helper = helper.getNext();}// first 指向第ranking个小孩，helper也跟着移动 ranking - 1位for (int i = 0; i < ranking - 1; i++) {first = first.getNext();helper = helper.getNext();}// 循环出队while (true) {// 只剩一个小孩时直接出队，并退出循环if (helper == first) {System.out.println(helper.getNo() + "出队");break;}// first和helper移动count-1位for (int i = 0; i < count - 1; i++) {first = first.getNext();System.out.println(first.getNo() + "出队");helper = helper.getNext();}// 出队first = first.getNext();helper.setNext(first);System.out.println();}}