给定一个排序的链表和一个要插入的值，编写一个函数以排序的方式插入该值。 初始链接列表
null
插入9后的链表
算法： 让输入链表按递增顺序排序。
1) If Linked list is empty then make the node as head and return it.2) If the value of the node to be inserted is smaller than the value of the head node, then insert the node at the start and make it head.3) In a loop, find the appropriate node after which the input node (let 9) is to be inserted. To find the appropriate node start from the head, keep moving until you reach a node GN (10 in the below diagram) who's value is greater than the input node. The node just before GN is theappropriate node (7).4) Insert the node (9) after the appropriate node (7) found in step 3.
实施：
C++
/* Program to insert in a sorted list */ #include <bits/stdc++.h> using namespace std; /* Link list node */ class Node { public : int data; Node* next; }; /* function to insert a new_node in a list. Note that this function expects a pointer to head_ref as this can modify the head of the input linked list (similar to push())*/ void sortedInsert(Node** head_ref, Node* new_node) { Node* current; /* Special case for the head end */ if (*head_ref == NULL || (*head_ref)->data >= new_node->data) { new_node->next = *head_ref; *head_ref = new_node; } else { /* Locate the node before the point of insertion */ current = *head_ref; while (current->next != NULL && current->next->data < new_node->data) { current = current->next; } new_node->next = current->next; current->next = new_node; } } /* BELOW FUNCTIONS ARE JUST UTILITY TO TEST sortedInsert */ /* A utility function to create a new node */ Node* newNode( int new_data) { /* allocate node */ Node* new_node = new Node(); /* put in the data */ new_node->data = new_data; new_node->next = NULL; return new_node; } /* Function to print linked list */ void printList(Node* head) { Node* temp = head; while (temp != NULL) { cout << temp->data << " " ; temp = temp->next; } } /* Driver program to test count function*/ int main() { /* Start with the empty list */ Node* head = NULL; Node* new_node = newNode(5); sortedInsert(&head, new_node); new_node = newNode(10); sortedInsert(&head, new_node); new_node = newNode(7); sortedInsert(&head, new_node); new_node = newNode(3); sortedInsert(&head, new_node); new_node = newNode(1); sortedInsert(&head, new_node); new_node = newNode(9); sortedInsert(&head, new_node); cout << "Created Linked List" ; printList(head); return 0; } // This is code is contributed by rathbhupendra |
C
/* Program to insert in a sorted list */ #include <stdio.h> #include <stdlib.h> /* Link list node */ struct Node { int data; struct Node* next; }; /* function to insert a new_node in a list. Note that this function expects a pointer to head_ref as this can modify the head of the input linked list (similar to push())*/ void sortedInsert( struct Node** head_ref, struct Node* new_node) { struct Node* current; /* Special case for the head end */ if (*head_ref == NULL || (*head_ref)->data >= new_node->data) { new_node->next = *head_ref; *head_ref = new_node; } else { /* Locate the node before the point of insertion */ current = *head_ref; while (current->next != NULL && current->next->data < new_node->data) { current = current->next; } new_node->next = current->next; current->next = new_node; } } /* BELOW FUNCTIONS ARE JUST UTILITY TO TEST sortedInsert */ /* A utility function to create a new node */ struct Node* newNode( int new_data) { /* allocate node */ struct Node* new_node = ( struct Node*) malloc ( sizeof ( struct Node)); /* put in the data */ new_node->data = new_data; new_node->next = NULL; return new_node; } /* Function to print linked list */ void printList( struct Node* head) { struct Node* temp = head; while (temp != NULL) { printf ( "%d " , temp->data); temp = temp->next; } } /* Driver program to test count function*/ int main() { /* Start with the empty list */ struct Node* head = NULL; struct Node* new_node = newNode(5); sortedInsert(&head, new_node); new_node = newNode(10); sortedInsert(&head, new_node); new_node = newNode(7); sortedInsert(&head, new_node); new_node = newNode(3); sortedInsert(&head, new_node); new_node = newNode(1); sortedInsert(&head, new_node); new_node = newNode(9); sortedInsert(&head, new_node); printf ( " Created Linked List" ); printList(head); return 0; } |
JAVA
// Java Program to insert in a sorted list class LinkedList { Node head; // head of list /* Linked list Node*/ class Node { int data; Node next; Node( int d) { data = d; next = null ; } } /* function to insert a new_node in a list. */ void sortedInsert(Node new_node) { Node current; /* Special case for head node */ if (head == null || head.data >= new_node.data) { new_node.next = head; head = new_node; } else { /* Locate the node before point of insertion. */ current = head; while (current.next != null && current.next.data < new_node.data) current = current.next; new_node.next = current.next; current.next = new_node; } } /*Utility functions*/ /* Function to create a node */ Node newNode( int data) { Node x = new Node(data); return x; } /* Function to print linked list */ void printList() { Node temp = head; while (temp != null ) { System.out.print(temp.data + " " ); temp = temp.next; } } /* Driver function to test above methods */ public static void main(String args[]) { LinkedList llist = new LinkedList(); Node new_node; new_node = llist.newNode( 5 ); llist.sortedInsert(new_node); new_node = llist.newNode( 10 ); llist.sortedInsert(new_node); new_node = llist.newNode( 7 ); llist.sortedInsert(new_node); new_node = llist.newNode( 3 ); llist.sortedInsert(new_node); new_node = llist.newNode( 1 ); llist.sortedInsert(new_node); new_node = llist.newNode( 9 ); llist.sortedInsert(new_node); System.out.println( "Created Linked List" ); llist.printList(); } } /* This code is contributed by Rajat Mishra */ |
python
# Python program to insert in a sorted list # Node class class Node: # Constructor to initialize the node object def __init__( self , data): self .data = data self . next = None class LinkedList: # Function to initialize head def __init__( self ): self .head = None def sortedInsert( self , new_node): # Special case for the empty linked list if self .head is None : new_node. next = self .head self .head = new_node # Special case for head at end elif self .head.data > = new_node.data: new_node. next = self .head self .head = new_node else : # Locate the node before the point of insertion current = self .head while (current. next is not None and current. next .data < new_node.data): current = current. next new_node. next = current. next current. next = new_node # Function to insert a new node at the beginning def push( self , new_data): new_node = Node(new_data) new_node. next = self .head self .head = new_node # Utility function to print it the LinkedList def printList( self ): temp = self .head while (temp): print temp.data, temp = temp. next # Driver program llist = LinkedList() new_node = Node( 5 ) llist.sortedInsert(new_node) new_node = Node( 10 ) llist.sortedInsert(new_node) new_node = Node( 7 ) llist.sortedInsert(new_node) new_node = Node( 3 ) llist.sortedInsert(new_node) new_node = Node( 1 ) llist.sortedInsert(new_node) new_node = Node( 9 ) llist.sortedInsert(new_node) print "Create Linked List" llist.printList() # This code is contributed by Nikhil Kumar Singh(nickzuck_007) |
C#
// C# Program to insert in a sorted list using System; public class LinkedList { Node head; // head of list /* Linked list Node*/ class Node { public int data; public Node next; public Node( int d) { data = d; next = null ; } } /* function to insert a new_node in a list. */ void sortedInsert(Node new_node) { Node current; /* Special case for head node */ if (head == null || head.data >= new_node.data) { new_node.next = head; head = new_node; } else { /* Locate the node before point of insertion. */ current = head; while (current.next != null && current.next.data < new_node.data) current = current.next; new_node.next = current.next; current.next = new_node; } } /*Utility functions*/ /* Function to create a node */ Node newNode( int data) { Node x = new Node(data); return x; } /* Function to print linked list */ void printList() { Node temp = head; while (temp != null ) { Console.Write(temp.data + " " ); temp = temp.next; } } /* Driver code */ public static void Main(String[] args) { LinkedList llist = new LinkedList(); Node new_node; new_node = llist.newNode(5); llist.sortedInsert(new_node); new_node = llist.newNode(10); llist.sortedInsert(new_node); new_node = llist.newNode(7); llist.sortedInsert(new_node); new_node = llist.newNode(3); llist.sortedInsert(new_node); new_node = llist.newNode(1); llist.sortedInsert(new_node); new_node = llist.newNode(9); llist.sortedInsert(new_node); Console.WriteLine( "Created Linked List" ); llist.printList(); } } /* This code is contributed by 29AjayKumar */ |
Javascript
<script> // javascript Program to insert in a sorted list var head; // head of list /* Linked list Node */ class Node { constructor(val) { this .data = val; this .next = null ; } } /* * function to insert a new_node in a list. */ function sortedInsert( new_node) { var current; /* Special case for head node */ if (head == null || head.data >= new_node.data) { new_node.next = head; head = new_node; } else { /* Locate the node before point of insertion. */ current = head; while (current.next != null && current.next.data < new_node.data) current = current.next; new_node.next = current.next; current.next = new_node; } } /* Utility functions */ /* Function to create a node */ function newNode(data) { x = new Node(data); return x; } /* Function to print linked list */ function printList() { temp = head; while (temp != null ) { document.write(temp.data + " " ); temp = temp.next; } } /* Driver function to test above methods */ var new_node; new_node = newNode(5); sortedInsert(new_node); new_node = newNode(10); sortedInsert(new_node); new_node = newNode(7); sortedInsert(new_node); new_node = newNode(3); sortedInsert(new_node); new_node = newNode(1); sortedInsert(new_node); new_node = newNode(9); sortedInsert(new_node); document.write( "Created Linked List<br/>" ); printList(); // This code is contributed by aashish1995 </script> |
输出：
Created Linked List1 3 5 7 9 10
复杂性分析：
- 时间复杂性： O（n）。 只需要遍历列表一次。
- 辅助空间： O（1）。 不需要额外的空间。
使用双指针的更短实现： 幸亏 穆拉特姆奥兹特克 为了提供这个解决方案。有关完整功能，请参见下面的Murat M Ozturk评论。代码使用双指针跟踪上一个节点的下一个指针（之后插入新节点）。 请注意，下面这行代码发生了变化 现在的 获取节点中下一个指针的地址。
current = &((*current)->next);
另外，请注意下面的评论。
/* Copies the value-at-address current to new_node's next pointer*/ new_node->next = *current; /* Fix next pointer of the node (using its address) after which new_node is being inserted */ *current = new_node;
时间复杂性： O（n） 参考资料： http://cslibrary.stanford.edu/105/LinkedListProblems.pdf
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
