java-链表排序

news/2024/9/24 16:30:30/

需求

在这里插入图片描述

思路

  • 排序:讲所有的值都取出来,存储到ArrayList中,然后排序,将排序之后的元素依次使用add方法添加到自定义链表
  • 合并排序:先合并,然后调用刚才写的排序算法
  • 合并:将表一的头结点作为新链表的头结点,表一的尾节点指向表二的头结点

代码

自定义链表

java">// 自定义一个链表
public class MyLinkedList<E> {Node<E> head = null;public Node<Integer> merge(Node<Integer> head1, Node<Integer> head2) {if (head1 == null ) {return head2;}if (head2 == null) {return head1;}// 直接将表一的头结点作为新链表的头结点,表一的尾节点指向表二的头结点Node<Integer> tmp = head1;while (tmp.next != null) {tmp = tmp.next;}tmp.next = head2;// 对新链表进行排序MyLinkedList<Integer> myLinkedList = new MyLinkedList<>();myLinkedList.head = head1;return myLinkedList.sorted();}//定义一个内部类public static class Node<E> {E data;Node<E> next;public Node(E data, Node<E> next) {this.data = data;this.next = next;}}// 添加一个元素public void add(E e) {Node<E> newNode = new Node<>(e, null);if (head == null) {head = newNode;return;}Node<E> temp = head;// 尾插法while (temp.next != null) {temp = temp.next;}temp.next = newNode;}public Node<E> sorted() {// 如果链表为空或者只有一个元素,直接返回if (head == null || head.next == null) {return head;}//定义一个新的list 存放数据List<E> list = new ArrayList<>();while (head != null) {list.add(head.data);head = head.next;}//对list进行排序list.sort((o1, o2) -> {if (o1 instanceof Integer) {return (Integer) o1 - (Integer) o2;}return 0;});//将排序后的数据重新放入链表MyLinkedList<E> myLinkedList = new MyLinkedList<>();for (E e : list) {myLinkedList.add(e);}return myLinkedList.head;}public static void forEachPrint(MyLinkedList.Node<Integer> sorted1) {while (sorted1 != null) {System.out.print(sorted1.data+" ");sorted1 = sorted1.next;}}
}

使用

java">public class Test {public static void main(String[] args) {// 第一个链表MyLinkedList myLinkedList1 = new MyLinkedList();myLinkedList1.add(2);myLinkedList1.add(4);myLinkedList1.add(1);// 获取头结点MyLinkedList.Node<Integer> head1 = myLinkedList1.head;// 第二个链表MyLinkedList myLinkedList2 = new MyLinkedList();myLinkedList2.add(9);myLinkedList2.add(1);myLinkedList2.add(3);// 获取头结点MyLinkedList.Node<Integer> head2 = myLinkedList2.head;//功能1:对两个链表排序,并且分别遍历输出MyLinkedList.Node<Integer> sorted1 = myLinkedList1.sorted();MyLinkedList.Node<Integer> sorted2 = myLinkedList2.sorted();System.out.println("排序后的链表1:");MyLinkedList.forEachPrint(sorted1);System.out.println();System.out.println("排序后的链表2:");MyLinkedList.forEachPrint(sorted2);//功能2:合并两个有序链表,合并后的链表依然有序,并且遍历输出MyLinkedList.Node<Integer> merge = myLinkedList1.merge(head1, head2);// 遍历输出System.out.println();System.out.println("合并后的链表:");MyLinkedList.forEachPrint(merge);}}

http://www.ppmy.cn/news/1442809.html

相关文章

【spring mvc】配置请求到视图名称转换器

最近在开发项目中遇到springmvc在进行视图渲染时&#xff0c;pc端和移动端不是同一个页面的情况&#xff0c;需要将不同的设备类型解析到不同的视图进行渲染。 一、配置方式 这里我写了一个RequestToViewNameTranslatorImpl类实现了RequestToViewNameTranslator接口&#xff…

node 项目启动报 ERROR Failed to compile with 1 errors 错误

问题 node项目通过npm run dev启动时出现ERROR Failed to compile with 1 errors 错误&#xff0c;具体信息如下&#xff1a; ✖ WebpackCompiled with some errors in 366.81msERROR Failed to compile with 1 errors …

基于单片机的多功能电子万年历系统

摘要:该题目要求学生综合运用单片机原理、低频电子线路、数字电路与逻辑设计等相关知识,设计完成多功能电子万年历系统。通过完成设计任务,使学生掌握单片机设计开发的基本流程,增强学生动手实践能力,培养学生分析和解决实际问题的能力,为后续课程的学习和工作打下良好基础。 关…

iOS 获取到scrollView停止拖动时候的速度

在 - (void)scrollViewWillEndDragging:(UIScrollView *)scrollView withVelocity:(CGPoint)velocity targetContentOffset:(inout CGPoint *)targetContentOffset { self.velocity velocity.y; } 方法中得到手势离开的时候的速度 - (void)scrollViewWillEndDragging:(UIScro…

盲人出行挑战与曙光:“盲人视觉辅助技术研发”助力无障碍生活

作为一名资深记者&#xff0c;我深感盲人朋友们在日常出行中面临的种种困难。然而&#xff0c;在科技日新月异的今天&#xff0c;一项名为蝙蝠避障的专为盲人视觉辅助技术研发的领域正在以前沿科技成果&#xff0c;为改善盲人出行困境带来希望之光。本文将深入探讨这一技术如何…

第八周学习笔记DAY.5-实用类介绍

String类 String类位于java.lang包中&#xff0c;具有丰富的方法&#xff1a;计算字符串的长度、比较字符串、连接字符串、提取字符串 length()方法 String类提供了length()方法&#xff0c;确定字符串的长度 equals()方法 String类提供了equals( )方法&#xff0c;比较存…

Windows下Git的使用

目录 一、克隆远程仓库到本地二、git的三板斧2.1 add-将代码添加到本地仓库2.2 commit-提交代码到本地仓库2.3 push-推送本次添加操作到远程仓库2.4 gitee只有三板斧吗&#xff1f; 三、推送后没有出现绿点四、push到远程时报错五、git图形化界面下载链接 一、克隆远程仓库到本…

数据结构-简单队列

1.简介 队列为一个有序列表&#xff0c;可以用数组或链表来实现。 先进先出原则。先存入队列的数据先取出&#xff0c;后存进队列的数据后取出。 这里对比一下&#xff0c;栈是后来者居上 下面使用数组来模拟队列&#xff0c;用数组的结构来存储队列的数据&#xff1a; Que…