常州网站价格,php网站实例教程,如何让网站显示404,景安一个空间怎么做多个网站问题
在一个循环链表中节点的值递增排序#xff0c;请设计一个算法在该循环链表中插入节点#xff0c;并保证插入节点之后的循环链表仍然是排序的。
分析
首先分析在排序的循环链表中插入节点的规律。当在图4.15#xff08;a#xff09;的链表中插入值为4的节点时…问题
在一个循环链表中节点的值递增排序请设计一个算法在该循环链表中插入节点并保证插入节点之后的循环链表仍然是排序的。
分析
首先分析在排序的循环链表中插入节点的规律。当在图4.15a的链表中插入值为4的节点时新的节点位于值为3的节点和值为5的节点之间。这很容易理解为了使插入新节点的循环链表仍然是排序的新节点的前一个节点的值应该比新节点的值小后一个节点的值应该比新节点的值大。
但是特殊情况需要特殊处理。如果新节点的值比链表中已有的最大值还要大那么新的节点将被插入最大值和最小值之间。如果新节点的值比链表中已有的最大值还要大那么新的节点将被插入最大值和最小值之间。 在上面的规则中总是先试图从链表中找到符合条件的相邻的两个节点。如果开始的时候链表中的节点数小于2那么应该有两种可能。第1种可能是开始的时候链表是空的一个节点都没有。此时插入一个新的节点该节点成为循环链表中的唯一节点那么next指针指向节点自己如图4.17a所示。第2种可能是开始的时候链表中只有一个节点插入一个新的节点之后两个节点的next指针互相指向对方如图4.17b所示。
解
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;}}
}
