链表（篇1）循环有序链表中插入节点

本文主要是介绍链表（篇1）循环有序链表中插入节点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在循环有序链表中插入一个新值。例如：

这里写图片描述

插入7之后

这里写图片描述

算法：
为新插入的节点分配内存，并将数据放在新分配的节点中。让指向新节点的指针是new_node。在内存分配之后，以下是需要处理的三种情况。

1）链接为空：  a）因为new_node是循环链表中的唯一节点，所以进行自循环。      new_node-> next = new_node;  b）更改头指针以指向新节点。head_ref = new_node;
2）新节点要在头节点之前插入：    （a）使用循环找出最后一个节点。while（current-> next！= * head_ref）current = current-> next;（b）更改最后一个节点的下一个。 current-> next = new_node;（c）将新节点的下一个更改为指向头。new_node-> next = * head_ref;（d）将头指针改变为指向新节点。* head_ref = new_node;
3）新节点要插入头部之后的某处：（a）找到要插入新节点的节点。while（current-> next！= * head_ref && current-> next-> data <new_node-> data）{current = current-> next; }}（b）将new_node的下一个作为定位指针的下一个new_node-> next = current-> next;（c）更改下一个的指针current-> next = new_node;

代码

// Java program for sorted insert in circular linked listclass Node
{int data;Node next;Node(int d){data = d;next = null;}
}class LinkedList
{Node head;// ConstructorLinkedList()   { head = null; }/* function to insert a new_node in a list in sorted way.Note that this function expects a pointer to head nodeas this can modify the head of the input linked list */void sortedInsert(Node new_node){Node current = head;// Case 1 of the above algoif (current == null){new_node.next = new_node;head = new_node;}// Case 2 of the above algoelse if (current.data >= new_node.data){/* If value is smaller than head's value thenwe need to change next of last node */while (current.next != head)current = current.next;current.next = new_node;new_node.next = head;head = new_node;}// Case 3 of the above algoelse{/* Locate the node before the point of insertion */while (current.next != head &&current.next.data < new_node.data)current = current.next;new_node.next = current.next;current.next = new_node;}}// Utility method to print a linked listvoid printList(){if (head != null){Node temp = head;do{System.out.print(temp.data + " ");temp = temp.next;}  while (temp != head);}}// Driver code to test abovepublic static void main(String[] args){LinkedList list = new LinkedList();// Creating the linkedlistint arr[] = new int[] {12, 56, 2, 11, 1, 90};/* start with empty linked list */Node temp = null;/* Create linked list from the array arr[].Created linked list will be 1->2->11->12->56->90*/for (int i = 0; i < 6; i++){temp = new Node(arr[i]);list.sortedInsert(temp);}list.printList();}
}