当前位置： 首页 > news >正文

4. 链表

news 2025/9/18 10:57:38

1. 哈希表

image

2. 有序表

image

代码示例

import java.util.TreeMap;public class Test{public static void main(String[] args) {TreeMap<Integer, String> treeMap = new TreeMap<>();treeMap.put(1, "我是1");treeMap.put(4, "我是4");treeMap.put(9, "我是9");treeMap.put(3, "我是3");treeMap.put(5, "我是5");System.out.println("有序表中是否包含5：" + treeMap.containsKey(5));System.out.println("有序表中最小数是：" + treeMap.firstKey());System.out.println("有序表中最大数是：" + treeMap.lastKey());System.out.println("在有序表中，所有 <= 8 的数中，离 8 最近的数是：" + treeMap.floorKey(8));System.out.println("在有序表中，所有 >= 8 的数中，离 8 最近的数是：" + treeMap.ceilingKey(8));System.out.println("在有序表中，所有 <= 7 的数中，离 7 最近的数是：" + treeMap.floorKey(8));System.out.println("在有序表中，所有 <= 7 的数中，离 7 最近的数是：" + treeMap.ceilingKey(8));System.out.println("有序表中key为9的字符串是：" + treeMap.get(9));}}

image

3. 链表

image
image

代码示例

import java.util.TreeMap;public class Test{// 单向链表public static class Node{public int value;public Node next;// 构造函数public Node(int data){this.value = data;}}// 双向链表public static class DoubleNode{public int value;public DoubleNode last;public DoubleNode next;public DoubleNode(int data){this.value = data;}}// 反转单链表public static Node reverseList(Node head){Node pre = null;Node nex = null;while(head != null){nex = head.next;head.next = pre;pre = head;head = nex;}return pre;}// 反转双链表// 函数重载public static DoubleNode reverseList(DoubleNode head){DoubleNode pre = null;DoubleNode nex = null;while(head != null){nex = head.next;head.next = pre;head.last = nex;pre = head;head = nex;}return pre;}// 输出单链表public static void printLinkedList(Node head){System.out.print("单链表的输出结果是：");while (head != null) {System.out.print(head.value + " ");head = head.next;}System.out.println();}// 输出双链表public static void printDoubleLinkedList(DoubleNode head){System.out.print("双链表的输出结果是：");DoubleNode end = null;while (head != null){System.out.print(head.value + " ");end = head;head = head.next;}System.out.println();System.out.print("双链表的输出结果是：");while (end != null){System.out.print(end.value + " ");end = end.last;}System.out.println();}// 主函数public static void main(String[] args) {// 插入链表数据Node head1 = new Node(1);head1.next = new Node(2);head1.next.next = new Node(3);printLinkedList(head1);head1 = reverseList(head1);printLinkedList(head1);System.out.println();DoubleNode head2 = new DoubleNode(2);head2.next = new DoubleNode(3);head2.next.last = head2;head2.next.next = new DoubleNode(4);head2.next.next.last = head2.next;head2.next.next.next = new DoubleNode(5);head2.next.next.next.last = head2.next.next;printDoubleLinkedList(head2);printDoubleLinkedList(reverseList(head2));}
}

image

代码示例

import java.util.TreeMap;public class Test{// 单向链表public static class Node{public int value;public Node next;// 构造函数public Node(int data){this.value = data;}}public static void samePart(Node node1, Node node2){System.out.print("两个单链表相同的值为：");while (node1 != null && node2 != null){if(node1.value < node2.value) node1 = node1.next;else if(node1.value > node2.value) node2 = node2.next;else {System.out.print(node1.value + " ");node1 = node1.next;node2 = node2.next;}}}public static void printLinkedList(Node head){System.out.print("单链表输出的结果是：");while (head != null){System.out.print(head.value + " ");head = head.next;}System.out.println();}// 主函数public static void main(String[] args) {// 插入链表数据Node node1 = new Node(2);node1.next = new Node(3);node1.next.next = new Node(5);node1.next.next.next = new Node(6);Node node2 = new Node(1);node2.next = new Node(2);node2.next.next = new Node(5);node2.next.next.next = new Node(7);node2.next.next.next.next = new Node(8);printLinkedList(node1);printLinkedList(node2);// 打印公共部分samePart(node1, node2);}
}

image

image

O（1）空间复杂度的实现方法图解如图所示：

image

代码示例

import java.util.Stack;
import java.util.TreeMap;public class Test{// 单向链表public static class Node{public int value;public Node next;// 构造函数public Node(int data){this.value = data;}}// o(N)的空间复杂度函数public static boolean isPalindrome1(Node head){Stack<Node> stack = new Stack<>();// 使用临时变量Node cur = head;while(cur != null){stack.push(cur);cur = cur.next;}while (head != null){if(head.value != stack.pop().value) {return false;}head = head.next;}return true;}// o(N/2)的空间复杂度函数public static boolean isPalindrome2(Node head) {if(head == null || head.next == null)return true;// 快慢指针找到中点位置Node right = head.next; // 用来记录中点位置Node cur = head;while (cur.next != null && cur.next.next != null){right = right.next;cur = cur.next.next;}Stack<Node> stack = new Stack<>();while (right != null){stack.push(right);right = right.next;}while (!stack.isEmpty()){if(head.value != stack.pop().value)return false;head = head.next;}return true;}// O(1)的空间复杂度函数public static boolean isPalindrome3(Node head) {if(head == null || head.next == null)return true;Node n1 = head;Node n2 = head;while(n2.next != null && n2.next.next != null){n1 = n1.next;n2 = n2.next.next;}n2 = n1.next;n1.next = null;Node n3 = null;// 列表的倒序while (n2 != null) {n3 = n2.next; // 记录下一个节点的位置n2.next = n1;n1 = n2;n2 = n3;}n3 = n1; // last noden2 = head; // first nodeboolean res = true;while (n1 != null && n2 != null){if(n1.value != n2.value){res = false;break;}n1 = n1.next;n2 = n2.next;}// 还原链表n1 = n3.next;n3.next = null;while (n1 != null){n2 = n1.next;n1.next = n3;n3 = n1;n1 = n2;}return res;}// 输出链表public static void printLinkedList(Node head){System.out.print("单链表输出的结果是：");while (head != null){System.out.print(head.value + " ");head = head.next;}System.out.println();}// 主函数public static void main(String[] args) {// 插入链表数据Node head = null;printLinkedList(head);System.out.print(isPalindrome1(head) + " | ");System.out.print(isPalindrome2(head) + " | ");System.out.println(isPalindrome3(head) + " | ");printLinkedList(head);System.out.println("=========================");head = new Node(1);printLinkedList(head);System.out.print(isPalindrome1(head) + " | ");System.out.print(isPalindrome2(head) + " | ");System.out.println(isPalindrome3(head) + " | ");printLinkedList(head);System.out.println("=========================");head = new Node(1);head.next = new Node(2);printLinkedList(head);System.out.print(isPalindrome1(head) + " | ");System.out.print(isPalindrome2(head) + " | ");System.out.println(isPalindrome3(head) + " | ");printLinkedList(head);System.out.println("=========================");head = new Node(1);head.next = new Node(1);printLinkedList(head);System.out.print(isPalindrome1(head) + " | ");System.out.print(isPalindrome2(head) + " | ");System.out.println(isPalindrome3(head) + " | ");printLinkedList(head);System.out.println("=========================");head = new Node(1);head.next = new Node(2);head.next.next = new Node(3);printLinkedList(head);System.out.print(isPalindrome1(head) + " | ");System.out.print(isPalindrome2(head) + " | ");System.out.println(isPalindrome3(head) + " | ");printLinkedList(head);System.out.println("=========================");head = new Node(1);head.next = new Node(2);head.next.next = new Node(1);printLinkedList(head);System.out.print(isPalindrome1(head) + " | ");System.out.print(isPalindrome2(head) + " | ");System.out.println(isPalindrome3(head) + " | ");printLinkedList(head);System.out.println("=========================");head = new Node(1);head.next = new Node(2);head.next.next = new Node(3);head.next.next.next = new Node(1);printLinkedList(head);System.out.print(isPalindrome1(head) + " | ");System.out.print(isPalindrome2(head) + " | ");System.out.println(isPalindrome3(head) + " | ");printLinkedList(head);System.out.println("=========================");head = new Node(1);head.next = new Node(2);head.next.next = new Node(2);head.next.next.next = new Node(1);printLinkedList(head);System.out.print(isPalindrome1(head) + " | ");System.out.print(isPalindrome2(head) + " | ");System.out.println(isPalindrome3(head) + " | ");printLinkedList(head);System.out.println("=========================");head = new Node(1);head.next = new Node(2);head.next.next = new Node(3);head.next.next.next = new Node(2);head.next.next.next.next = new Node(1);printLinkedList(head);System.out.print(isPalindrome1(head) + " | ");System.out.print(isPalindrome2(head) + " | ");System.out.println(isPalindrome3(head) + " | ");printLinkedList(head);System.out.println("=========================");}
}

image

代码示例
http://www.wxhsa.cn/company.asp?id=816

相关文章：

  • Maven-和-Eclipse-全-
  • Prompt、RAG、微调
  • 飞书对程序员下手了，0 代码生成各类系统！！
  • 测试用例设计检查项
  • Android Kotlin请求权限及权限回调处理
  • 版本发布｜ IvorySQL 4.6 发布
  • Avalonia Calendar 日历控件遇到 Flyout 或者切换页面时出现的鼠标按下失效的解决方法
  • cache和主存的映射方式
  • Vue 2 + Element UI 技术栈的管理端项目和Git使用教程
  • 你好
  • 2025年图像、信号处理与机器学习国际学术会议（ISPML 2025）
  • 利用Ampere Altra与SpinKube实现可扩展工作流的突破性实践
  • 有向距离场SDF，在游戏中如何实现agent导航以及绕障
  • ubuntu22.04.5系统重启后网络配置消失问题
  • 第十届计算机技术与机械电气工程国际学术论坛（ISCME 2025）暨2025年泰山学术论坛-鲁东大学微纳传感器及系统专题论坛
  • SLB和NAT网关的作用
  • 基于Python+Vue开发的音乐推荐管理系统源码+运行
  • linux 系统下iperf 测试网卡性能优化步骤
  • FinRL（2）China_A_share_market_tushare.ipynb
  • 应急响应：某网站被挂非法链接
  • 笔记-每天进步一点
  • 用惯了VO，什么时候需要DTO？
  • 剑指offer-29、最⼩的k个数
  • 【初赛】时间复杂度 - Slayer
  • 微调
  • WPF 警惕 StylusPlugIn 的多线程安全问题
  • 【译】Visual Studio 八月更新已发布 —— 更智能的人工智能、更出色的调试功能以及更多控制权
  • RAG or 微调
  • 什么是AI CRM（人工智能客户关系管理）
  • 完整教程：WPF WriteableBitmap 高性能双缓冲图片显示方案