给定一个包含 N 节点。问题是插入一个包含数据的新节点 十、 在列表的中间。如果 N 如果是偶数，则在 （n/2） 第个节点，否则在 （n+1）/2 第四节点。
null
例如：
Input : list: 1->2->4->5 x = 3Output : 1->2->3->4->5Input : list: 5->10->4->32->16 x = 41Output : 5->10->4->41->32->16
方法1（使用链表的长度）： 使用一次遍历查找链接的节点数或长度。顺其自然 伦恩 计算 C =（len/2），如果 伦恩 是甚至，否则 C =（len+1）/2，如果 伦恩 这很奇怪。第一次再横穿一遍 C 节点，并在 C 第四节点。
C++
// C++ implementation to insert node at the middle // of the linked list #include <bits/stdc++.h> using namespace std; // structure of a node struct Node { int data; Node* next; }; // function to create and return a node Node* getNode( int data) { // allocating space Node* newNode = (Node*) malloc ( sizeof (Node)); // inserting the required data newNode->data = data; newNode->next = NULL; return newNode; } // function to insert node at the middle // of the linked list void insertAtMid(Node** head_ref, int x) { // if list is empty if (*head_ref == NULL) *head_ref = getNode(x); else { // get a new node Node* newNode = getNode(x); Node* ptr = *head_ref; int len = 0; // calculate length of the linked list //, i.e, the number of nodes while (ptr != NULL) { len++; ptr = ptr->next; } // 'count' the number of nodes after which // the new node is to be inserted int count = ((len % 2) == 0) ? (len / 2) : (len + 1) / 2; ptr = *head_ref; // 'ptr' points to the node after which // the new node is to be inserted while (count-- > 1) ptr = ptr->next; // insert the 'newNode' and adjust the // required links newNode->next = ptr->next; ptr->next = newNode; } } // function to display the linked list void display(Node* head) { while (head != NULL) { cout << head->data << " " ; head = head->next; } } // Driver program to test above int main() { // Creating the list 1->2->4->5 Node* head = NULL; head = getNode(1); head->next = getNode(2); head->next->next = getNode(4); head->next->next->next = getNode(5); cout << "Linked list before insertion: " ; display(head); int x = 3; insertAtMid(&head, x); cout << "Linked list after insertion: " ; display(head); return 0; } |
JAVA
// Java implementation to insert node // at the middle of the linked list import java.util.*; import java.lang.*; import java.io.*; class LinkedList { static Node head; // head of list /* Node Class */ static class Node { int data; Node next; // Constructor to create a new node Node( int d) { data = d; next = null ; } } // function to insert node at the // middle of the linked list static void insertAtMid( int x) { // if list is empty if (head == null ) head = new Node(x); else { // get a new node Node newNode = new Node(x); Node ptr = head; int len = 0 ; // calculate length of the linked list //, i.e, the number of nodes while (ptr != null ) { len++; ptr = ptr.next; } // 'count' the number of nodes after which // the new node is to be inserted int count = ((len % 2 ) == 0 ) ? (len / 2 ) : (len + 1 ) / 2 ; ptr = head; // 'ptr' points to the node after which // the new node is to be inserted while (count-- > 1 ) ptr = ptr.next; // insert the 'newNode' and adjust // the required links newNode.next = ptr.next; ptr.next = newNode; } } // function to display the linked list static void display() { Node temp = head; while (temp != null ) { System.out.print(temp.data + " " ); temp = temp.next; } } // Driver program to test above public static void main (String[] args) { // Creating the list 1.2.4.5 head = null ; head = new Node( 1 ); head.next = new Node( 2 ); head.next.next = new Node( 4 ); head.next.next.next = new Node( 5 ); System.out.println( "Linked list before " + "insertion: " ); display(); int x = 3 ; insertAtMid(x); System.out.println( "Linked list after" + " insertion: " ); display(); } } // This article is contributed by Chhavi |
Python3
# Python3 implementation to insert node # at the middle of a linked list # Node class class Node: # constructor to create a new node def __init__( self , data): self .data = data self . next = None # function to insert node at the # middle of linked list given the head def insertAtMid(head, x): if (head = = None ): #if the list is empty head = Node(x) else : # create a new node for the value # to be inserted newNode = Node(x) ptr = head length = 0 # calculate the length of the linked # list while (ptr ! = None ): ptr = ptr. next length + = 1 # 'count' the number of node after which # the new node has to be inserted if (length % 2 = = 0 ): count = length / 2 else : (length + 1 ) / 2 ptr = head # move ptr to the node after which # the new node has to inserted while (count > 1 ): count - = 1 ptr = ptr. next # insert the 'newNode' and adjust # links accordingly newNode. next = ptr. next ptr. next = newNode # function to display the linked list def display(head): temp = head while (temp ! = None ): print ( str (temp.data), end = " " ) temp = temp. next # Driver Code # Creating the linked list 1.2.4.5 head = Node( 1 ) head. next = Node( 2 ) head. next . next = Node( 4 ) head. next . next . next = Node( 5 ) print ( "Linked list before insertion: " , end = "") display(head) # inserting 3 in the middle of the linked list. x = 3 insertAtMid(head, x) print ( "Linked list after insertion: " , end = "") display(head) # This code is contributed by Pranav Devarakonda |
C#
// C# implementation to insert node // at the middle of the linked list using System; public class LinkedList { static Node head; // head of list /* Node Class */ public class Node { public int data; public Node next; // Constructor to create a new node public Node( int d) { data = d; next = null ; } } // function to insert node at the // middle of the linked list static void insertAtMid( int x) { // if list is empty if (head == null ) head = new Node(x); else { // get a new node Node newNode = new Node(x); Node ptr = head; int len = 0; // calculate length of the linked list //, i.e, the number of nodes while (ptr != null ) { len++; ptr = ptr.next; } // 'count' the number of nodes after which // the new node is to be inserted int count = ((len % 2) == 0) ? (len / 2) : (len + 1) / 2; ptr = head; // 'ptr' points to the node after which // the new node is to be inserted while (count-- > 1) ptr = ptr.next; // insert the 'newNode' and adjust // the required links newNode.next = ptr.next; ptr.next = newNode; } } // function to display the linked list static void display() { Node temp = head; while (temp != null ) { Console.Write(temp.data + " " ); temp = temp.next; } } // Driver code public static void Main () { // Creating the list 1.2.4.5 head = null ; head = new Node(1); head.next = new Node(2); head.next.next = new Node(4); head.next.next.next = new Node(5); Console.WriteLine( "Linked list before " + "insertion: " ); display(); int x = 3; insertAtMid(x); Console.WriteLine( "Linked list after" + " insertion: " ); display(); } } /* This code contributed by PrinciRaj1992 */ |
Javascript
<script> // Javascript implementation to insert node // at the middle of the linked list var head; // head of list /* Node Class */ class Node { // Constructor to create a new node constructor(d) { this .data = d; this .next = null ; } } // function to insert node at the // middle of the linked list function insertAtMid(x) { // if list is empty if (head == null ) head = new Node(x); else { // get a new node var newNode = new Node(x); var ptr = head; var len = 0; // calculate length of the linked list // , i.e, the number of nodes while (ptr != null ) { len++; ptr = ptr.next; } // 'count' the number of nodes after which // the new node is to be inserted var count = ((len % 2) == 0) ? (len / 2) : (len + 1) / 2; ptr = head; // 'ptr' points to the node after which // the new node is to be inserted while (count-- > 1) ptr = ptr.next; // insert the 'newNode' and adjust // the required links newNode.next = ptr.next; ptr.next = newNode; } } // function to display the linked list function display() { var temp = head; while (temp != null ) { document.write(temp.data + " " ); temp = temp.next; } } // Driver program to test above // Creating the list 1.2.4.5 head = new Node(1); head.next = new Node(2); head.next.next = new Node(4); head.next.next.next = new Node(5); document.write( "Linked list before " + "insertion: " ); display(); var x = 3; insertAtMid(x); document.write( "<br/>Linked list after" + " insertion: " ); display(); // This code contributed by Rajput-Ji </script> |
输出：
Linked list before insertion: 1 2 4 5Linked list after insertion: 1 2 3 4 5
时间复杂性： O（n）
方法2（使用两个指针）： 基于龟兔算法，该算法使用两个指针，一个称为 缓慢的 另一个被称为 快速的 .该算法有助于找到链表的中间节点。这在前面和黑色分割程序中进行了说明 这 邮递现在，您可以在上述过程中获得的中间节点之后插入新节点。这种方法只需要遍历列表一次。
C++
// C++ implementation to insert node at the middle // of the linked list #include <bits/stdc++.h> using namespace std; // structure of a node struct Node { int data; Node* next; }; // function to create and return a node Node* getNode( int data) { // allocating space Node* newNode = (Node*) malloc ( sizeof (Node)); // inserting the required data newNode->data = data; newNode->next = NULL; return newNode; } // function to insert node at the middle // of the linked list void insertAtMid(Node** head_ref, int x) { // if list is empty if (*head_ref == NULL) *head_ref = getNode(x); else { // get a new node Node* newNode = getNode(x); // assign values to the slow and fast // pointers Node* slow = *head_ref; Node* fast = (*head_ref)->next; while (fast && fast->next) { // move slow pointer to next node slow = slow->next; // move fast pointer two nodes at a time fast = fast->next->next; } // insert the 'newNode' and adjust the // required links newNode->next = slow->next; slow->next = newNode; } } // function to display the linked list void display(Node* head) { while (head != NULL) { cout << head->data << " " ; head = head->next; } } // Driver program to test above int main() { // Creating the list 1->2->4->5 Node* head = NULL; head = getNode(1); head->next = getNode(2); head->next->next = getNode(4); head->next->next->next = getNode(5); cout << "Linked list before insertion: " ; display(head); int x = 3; insertAtMid(&head, x); cout << "Linked list after insertion: " ; display(head); return 0; } |
JAVA
// Java implementation to insert node // at the middle of the linked list import java.util.*; import java.lang.*; import java.io.*; class LinkedList { static Node head; // head of list /* Node Class */ static class Node { int data; Node next; // Constructor to create a new node Node( int d) { data = d; next = null ; } } // function to insert node at the // middle of the linked list static void insertAtMid( int x) { // if list is empty if (head == null ) head = new Node(x); else { // get a new node Node newNode = new Node(x); // assign values to the slow // and fast pointers Node slow = head; Node fast = head.next; while (fast != null && fast.next != null ) { // move slow pointer to next node slow = slow.next; // move fast pointer two nodes // at a time fast = fast.next.next; } // insert the 'newNode' and adjust // the required links newNode.next = slow.next; slow.next = newNode; } } // function to display the linked list static void display() { Node temp = head; while (temp != null ) { System.out.print(temp.data + " " ); temp = temp.next; } } // Driver program to test above public static void main (String[] args) { // Creating the list 1.2.4.5 head = null ; head = new Node( 1 ); head.next = new Node( 2 ); head.next.next = new Node( 4 ); head.next.next.next = new Node( 5 ); System.out.println( "Linked list before" + " insertion: " ); display(); int x = 3 ; insertAtMid(x); System.out.println( "Linked list after" + " insertion: " ); display(); } } // This article is contributed by Chhavi |
Python3
# Python implementation to insert node # at the middle of the linked list # Node Class class Node : def __init__( self , d): self .data = d self . next = None class LinkedList: # function to insert node at the # middle of the linked list def __init__( self ): self .head = None # 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 def insertAtMid( self , x): # if list is empty if ( self .head = = None ): self .head = Node(x) else : # get a new node newNode = Node(x) # assign values to the slow # and fast pointers slow = self .head fast = self .head. next while (fast ! = None and fast. next ! = None ): # move slow pointer to next node slow = slow. next # move fast pointer two nodes # at a time fast = fast. next . next # insert the 'newNode' and # adjust the required links newNode. next = slow. next slow. next = newNode # function to display the linked list def display( self ): temp = self .head while (temp ! = None ): print (temp.data, end = " " ), temp = temp. next # Driver Code # Creating the list 1.2.4.5 ll = LinkedList() ll.push( 5 ) ll.push( 4 ) ll.push( 2 ) ll.push( 1 ) print ( "Linked list before insertion: " ), ll.display() x = 3 ll.insertAtMid(x) print ( "Linked list after insertion: " ), ll.display() # This code is contributed by prerna saini |
C#
// C# implementation to insert node // at the middle of the linked list using System; public class LinkedList { static Node head; // head of list /* Node Class */ class Node { public int data; public Node next; // Constructor to create a new node public Node( int d) { data = d; next = null ; } } // function to insert node at the // middle of the linked list static void insertAtMid( int x) { // if list is empty if (head == null ) head = new Node(x); else { // get a new node Node newNode = new Node(x); // assign values to the slow // and fast pointers Node slow = head; Node fast = head.next; while (fast != null && fast.next != null ) { // move slow pointer to next node slow = slow.next; // move fast pointer two nodes // at a time fast = fast.next.next; } // insert the 'newNode' and adjust // the required links newNode.next = slow.next; slow.next = newNode; } } // function to display the linked list static void display() { Node temp = head; while (temp != null ) { Console.Write(temp.data + " " ); temp = temp.next; } } // Driver code public static void Main (String[] args) { // Creating the list 1.2.4.5 head = null ; head = new Node(1); head.next = new Node(2); head.next.next = new Node(4); head.next.next.next = new Node(5); Console.WriteLine( "Linked list before" + " insertion: " ); display(); int x = 3; insertAtMid(x); Console.WriteLine( "Linked list after" + " insertion: " ); display(); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // Javascript implementation to insert node // at the middle of the linked list var head; // head of list /* Node Class */ class Node { // Constructor to create a new node constructor(val) { this .data = val; this .next = null ; } } // function to insert node at the // middle of the linked list function insertAtMid(x) { // if list is empty if (head == null ) head = new Node(x); else { // get a new node var newNode = new Node(x); // assign values to the slow // and fast pointers var slow = head; var fast = head.next; while (fast != null && fast.next != null ) { // move slow pointer to next node slow = slow.next; // move fast pointer two nodes // at a time fast = fast.next.next; } // insert the 'newNode' and adjust // the required links newNode.next = slow.next; slow.next = newNode; } } // function to display the linked list function display() { var temp = head; while (temp != null ) { document.write(temp.data + " " ); temp = temp.next; } } // Driver program to test above // Creating the list 1.2.4.5 head = null ; head = new Node(1); head.next = new Node(2); head.next.next = new Node(4); head.next.next.next = new Node(5); document.write( "Linked list before" + " insertion: " ); display(); var x = 3; insertAtMid(x); document.write( "<br/>Linked list after" + " insertion: " ); display(); // This code is contributed by todaysgaurav </script> |
输出：
Linked list before insertion: 1 2 4 5Linked list after insertion: 1 2 3 4 5
时间复杂性： O（n）
本文由 阿尤什·焦哈里 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
