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

面试算法29:排序的循环链表

问题

在一个循环链表中节点的值递增排序,请设计一个算法在该循环链表中插入节点,并保证插入节点之后的循环链表仍然是排序的。
在这里插入图片描述

分析

首先分析在排序的循环链表中插入节点的规律。当在图4.15(a)的链表中插入值为4的节点时,新的节点位于值为3的节点和值为5的节点之间。这很容易理解,为了使插入新节点的循环链表仍然是排序的,新节点的前一个节点的值应该比新节点的值小,后一个节点的值应该比新节点的值大。

但是特殊情况需要特殊处理。如果新节点的值比链表中已有的最大值还要大,那么新的节点将被插入最大值和最小值之间。如果新节点的值比链表中已有的最大值还要大,那么新的节点将被插入最大值和最小值之间。
在这里插入图片描述
在上面的规则中,总是先试图从链表中找到符合条件的相邻的两个节点。如果开始的时候链表中的节点数小于2,那么应该有两种可能。第1种可能是开始的时候链表是空的,一个节点都没有。此时插入一个新的节点,该节点成为循环链表中的唯一节点,那么next指针指向节点自己,如图4.17(a)所示。第2种可能是开始的时候链表中只有一个节点,插入一个新的节点之后,两个节点的next指针互相指向对方,如图4.17(b)所示。
在这里插入图片描述

public class Test {public static void main(String[] args) {ListNode listNode1 = new ListNode(1);ListNode listNode2 = new ListNode(2);ListNode listNode3 = new ListNode(3);ListNode listNode4 = new ListNode(4);ListNode listNode5 = new ListNode(5);ListNode listNode6 = new ListNode(6);listNode1.next = listNode2;listNode2.next = listNode3;listNode3.next = listNode5;listNode5.next = listNode6;listNode6.next = listNode1;ListNode result = insert(listNode1, 4);while (result != null) {System.out.println(result.val);result = result.next;}}public static ListNode insert(ListNode head, int insertVal) {ListNode node = new ListNode(insertVal);if (head == null) {// 没有节点head = node;head.next = head;}else if (head.next == head) {// 只有一个节点head.next = node;node.next = head;}else {insertCore(head, node);}return head;}private static void insertCore(ListNode head, ListNode node) {ListNode cur = head;ListNode next = head.next;ListNode biggest = head;while (!(cur.val <= node.val && next.val >= node.val) && next != head) {cur = next;next = next.next;if (cur.val >= biggest.val)biggest = cur;}if (cur.val <= node.val && next.val >= node.val) {cur.next = node;node.next = next;}else {node.next = biggest.next;biggest.next = node;}}
}
http://www.lryc.cn/news/198134.html

相关文章:

  • python中不可变类型和可变类型
  • vue3封装Axios库的 API 请求并使用拦截器来处理请求和响应
  • RK3588开发笔记(二):基于方案商提供sdk搭建引入mpp和sdk的宿主机交叉编译Qt5.12.10环境
  • rust学习——函数返回值
  • 【Cadence】配置文件cdsinit和cdsenv的使用
  • 软考 系统架构设计师系列知识点之基于架构的软件开发方法ABSD(6)
  • MATLAB常用命令大全,非常详细(持续更新中)
  • js笔试面试题5道附答案
  • 4-k8s-部署springboot项目简单实践
  • Ai数字人直播系统SaaS源码大开源,源码独立部署助力中小企业发展!
  • 新的 Work Node 如何加入 K8s 集群 - Kubeadm ?
  • laravel框架的优缺点是什么?
  • 程序员接单都在用这六大平台,你呢?
  • 2022年亚太杯APMCM数学建模大赛D题储能系统中传热翅片的结构优化求解全过程文档及程序
  • 图像处理软件Photoshop 2023 mac新增功能 ps 2023中文版
  • CSS基本讲解与使用(详解)
  • 最新AI创作系统ChatGPT源码+搭建部署教程+支持GPT4.0+支持ai绘画(Midjourney)/支持Prompt
  • Linux系统之部署SSCMS内容管理系统并实现外网访问
  • JVS-rules中的基础与复合变量:规则引擎的心脏
  • RN:指定模拟器启动
  • 【ARM Cache 系列文章 10 -- ARM Cortex-A720 Hunter 介绍】
  • 深度学习——残差网络(ResNet)
  • [java进阶]——IO流,递归实现多级文件拷贝
  • Linux创建与删除用户
  • 对传感器采样数据的低通滤波
  • Java开发树结构数据封装!
  • c++学习笔记汇总
  • [动手学深度学习]生成对抗网络GAN学习笔记
  • Kotlin中的算数运算符
  • Linux高性能服务器编程 学习笔记 第十六章 服务器调制、调试和测试