先看代码：
package top.baikunlong.top.baikunlong.linkedlist; import java.util.ArrayList; import java.util.Collections; /** * @author baikunlong * @date 2020/10/8 10:26 */ public class SingleLinkedList { /** * 头指针 */ private Node head = new Node(0, "头指针"); /** * 在最后添加节点 * * @param node */ public void add(Node node) { //首先找到最后个节点 Node temp = head;//头节点不能移动，需要临时变量 while (true) { if (temp.next == null) {//如果是最后个则添加 temp.next = node; break; } else { temp = temp.next;//否则移动到下一个节点 } } } /** * 根据序号插入 * * @param node */ public void addByNo(Node node) { Node temp = this.head; while (true) { if (temp.next == null) {//如果到了链表尾部，直接添加 temp.next = node; return; } else if (temp.next.no > node.no) {//如果当前节点的next.no大于node.no，则在当前节点后添加node node.next = temp.next; temp.next = node; return; } else if (temp.next.no == node.no) { //如果等于则提示已存在 System.out.printf("已存在 no=%d 的节点\n", node.no); return; } //如果均不是则往下遍历 temp = temp.next; } } /** * 根据no删除 * * @param no */ public void deleteByNo(int no) { Node temp = this.head; while (true) { if (temp.next == null) { System.out.printf("节点为 no=%d 不存在\n", no); return; } if (temp.next.no == no) { temp.next = temp.next.next; return; } temp = temp.next; } } /** * 根据no更新 * * @param node */ public void updateByNo(Node node) { Node temp = this.head.next; while (true) { if (temp == null) { System.out.printf("节点为 no=%d 不存在\n", node.no); return; } else if (temp.no == node.no) { temp.name = node.name; return; } temp = temp.next; } } /** * 根据no获取 * * @param no * @return */ public Node getNodeByNo(int no) { Node temp = this.head.next; while (true) { if (temp == null) { throw new RuntimeException("节点为 no=" + no + " 不存在"); } else if (temp.no == no) { return temp; } temp = temp.next; } } /** * 打印链表 */ public void list() { if (head.next == null) System.out.println("链表为空"); Node temp = head.next; while (true) { if (temp == null) { break; } else { System.out.println(temp.toString()); temp = temp.next; } } } /** * 链表长度 * * @return */ public int length() { if (head.next == null) return 0; Node temp = this.head.next; int length = 0; while (temp != null) { length++; temp = temp.next; } return length; } /** * 获取倒数第index个node * * @param index 倒数下标 * @return */ public Node getNodeByLastIndex(int index) { int length = length(); if (index > length || index < 1) { return null; } Node temp = this.head.next; for (int i = 0; i < length - index; i++) { temp = temp.next; } return temp; } /** * 反转链表 */ public void reverse() { //当前节点 Node currentNode = this.head.next; //用于存储当前节点的下一个节点 Node next; //创建个新头，相当于一条新链表 Node reverseHead = new Node(0, "反转链表的头节点"); while (currentNode != null) { next = currentNode.next;//存储当前节点的下一个节点，等会currentNode下一个节点会变化 //这两句实现了把新节点插入到头节点的next域，也就是最后进来的，放在了最前面，也就实现了反转 currentNode.next = reverseHead.next;//currentNode的下一节点指向反转链表的头节点的下一节点 reverseHead.next = currentNode;//再反转链表的头节点的下一节点指向currentNode currentNode = next;//当前节点向后走 } this.head.next = reverseHead.next; } /** * 添加有序链表，保证合并后还是有序 */ public void orderedAddAll(SingleLinkedList list) { Node tHead = this.head; Node oldNode = this.head.next;//被合并链表的第一个节点 Node newNode = list.head.next;//合并链表的第一个节点 while (oldNode != null || newNode != null) { //如果其中一个链表到尾了，直接把剩余的那个链表加进去 if (oldNode == null) { tHead.next = newNode; newNode = newNode.next; } else if (newNode == null) { tHead.next = oldNode; oldNode = oldNode.next; } else if (oldNode.no <= newNode.no) {//如果小于等于则把被合并链表的节点添加进去 tHead.next = oldNode; oldNode = oldNode.next; } else { tHead.next = newNode; newNode = newNode.next; } tHead=tHead.next; } } public static void main(String[] args) { SingleLinkedList list = new SingleLinkedList(); // System.out.println("按末尾添加："); // Node node = new Node(1, "张三"); // Node node2 = new Node(2, "李四"); // Node node3 = new Node(3, "王五"); // list.add(node); // list.add(node2); // list.add(node3); System.out.println("按no序号添加："); Node node = new Node(1, "张三"); Node node3 = new Node(3, "王五"); Node node2 = new Node(2, "李四"); list.addByNo(node); list.addByNo(node3); list.addByNo(node2); list.list(); list.deleteByNo(3); System.out.println("删除3后"); list.list(); System.out.println("删除33后"); list.deleteByNo(33); list.list(); System.out.println("更新2后"); node2.name = "李小四"; list.updateByNo(node2); list.list(); System.out.println("获取no=1"); System.out.println(list.getNodeByNo(1).toString()); System.out.println("长度：" + list.length()); System.out.println("倒数第一个：" + list.getNodeByLastIndex(1)); System.out.println("倒数第二个：" + list.getNodeByLastIndex(2)); System.out.println("倒数第三个：" + list.getNodeByLastIndex(3)); System.out.println("添加几条数据："); list.add(new Node(10, "测试10")); list.add(new Node(20, "测试20")); list.add(new Node(30, "测试30")); list.list(); System.out.println("反转链表："); list.reverse(); list.list(); //合并有序的 SingleLinkedList list2 = new SingleLinkedList(); list2.addByNo(new Node(1,"111")); list2.addByNo(new Node(3,"333")); list2.addByNo(new Node(7,"777")); list2.addByNo(new Node(9,"999")); list2.addByNo(new Node(5,"555")); SingleLinkedList list3 = new SingleLinkedList(); list3.addByNo(new Node(2,"222")); list3.addByNo(new Node(4,"444")); list3.addByNo(new Node(0,"000")); list3.addByNo(new Node(6,"666")); list2.orderedAddAll(list3); System.out.println("合并有序链表list2和list3："); list2.list(); } } /** * 节点类 */ class Node { public int no; public String name; public Node next; public Node(int no, String name) { this.no = no; this.name = name; } @Override public String toString() { return "Node{" + "no=" + no + ", name='" + name + '\'' + '}'; } }
反转有一定难度，看着图比较好理解：
