给定一个单链接列表，删除链接列表的中间部分。例如，如果给定的链表是1->2->3->4->5，那么链表应该修改为1->2->4->5
null
如果有偶数个节点，那么将有两个中间节点，我们需要删除第二个中间元素。例如，如果给定的链表是1->2->3->4->5->6，那么它应该被修改为1->2->3->5->6。 如果输入链表为空，则应保持为空。
如果输入链表有1个节点，则应删除该节点并返回新的头。
简单的解决方案： 其思想是首先计算链表中的节点数，然后使用简单的删除过程删除第n/2个节点。
C++14
// C++ program to delete middle // of a linked list #include <bits/stdc++.h> using namespace std; /* Link list Node */ struct Node { int data; struct Node* next; }; // count of nodes int countOfNodes( struct Node* head) { int count = 0; while (head != NULL) { head = head->next; count++; } return count; } // Deletes middle node and returns // head of the modified list struct Node* deleteMid( struct Node* head) { // Base cases if (head == NULL) return NULL; if (head->next == NULL) { delete head; return NULL; } struct Node* copyHead = head; // Find the count of nodes int count = countOfNodes(head); // Find the middle node int mid = count / 2; // Delete the middle node while (mid-- > 1) { head = head->next; } // Delete the middle node head->next = head->next->next; return copyHead; } // A utility function to print // a given linked list void printList( struct Node* ptr) { while (ptr != NULL) { cout << ptr->data << "->" ; ptr = ptr->next; } cout << "NULL" ; } // Utility function to create a new node. Node* newNode( int data) { struct Node* temp = new Node; temp->data = data; temp->next = NULL; return temp; } /* Driver program to test above function*/ int main() { /* Start with the empty list */ struct Node* head = newNode(1); head->next = newNode(2); head->next->next = newNode(3); head->next->next->next = newNode(4); cout << "Given Linked List" ; printList(head); head = deleteMid(head); cout << "Linked List after deletion of middle" ; printList(head); return 0; } |
JAVA
// Java program to delete middle // of a linked list import java.io.*; class GFG { /* Link list Node */ static class Node { int data; Node next; } // Utility function to create a new node. static Node newNode( int data) { Node temp = new Node(); temp.data = data; temp.next = null ; return temp; } // count of nodes static int countOfNodes(Node head) { int count = 0 ; while (head != null ) { head = head.next; count++; } return count; } // Deletes middle node and returns // head of the modified list static Node deleteMid(Node head) { // Base cases if (head == null ) return null ; if (head.next == null ) { return null ; } Node copyHead = head; // Find the count of nodes int count = countOfNodes(head); // Find the middle node int mid = count / 2 ; // Delete the middle node while (mid-- > 1 ) { head = head.next; } // Delete the middle node head.next = head.next.next; return copyHead; } // A utility function to print // a given linked list static void printList(Node ptr) { while (ptr != null ) { System.out.print(ptr.data + "->" ); ptr = ptr.next; } System.out.println( "NULL" ); } /* Driver code*/ public static void main(String[] args) { /* Start with the empty list */ Node head = newNode( 1 ); head.next = newNode( 2 ); head.next.next = newNode( 3 ); head.next.next.next = newNode( 4 ); System.out.println( "Given Linked List" ); printList(head); head = deleteMid(head); System.out.println( "Linked List after deletion of middle" ); printList(head); } } // This code is contributed by rajsanghavi9. |
Python3
# Python3 program to delete middle # of a linked list # Link list Node class Node: def __init__( self ): self .data = 0 self . next = None # Count of nodes def countOfNodes(head): count = 0 while (head ! = None ): head = head. next count + = 1 return count # Deletes middle node and returns # head of the modified list def deleteMid(head): # Base cases if (head = = None ): return None if (head. next = = None ): del head return None copyHead = head # Find the count of nodes count = countOfNodes(head) # Find the middle node mid = count / / 2 # Delete the middle node while (mid > 1 ): mid - = 1 head = head. next # Delete the middle node head. next = head. next . next return copyHead # A utility function to print # a given linked list def printList(ptr): while (ptr ! = None ): print (ptr.data, end = '->' ) ptr = ptr. next print ( 'NULL' ) # Utility function to create a new node. def newNode(data): temp = Node() temp.data = data temp. next = None return temp # Driver Code if __name__ = = '__main__' : # Start with the empty list head = newNode( 1 ) head. next = newNode( 2 ) head. next . next = newNode( 3 ) head. next . next . next = newNode( 4 ) print ( "Given Linked List" ) printList(head) head = deleteMid(head) print ( "Linked List after deletion of middle" ) printList(head) # This code is contributed by rutvik_56 |
C#
// C# program to delete middle of a linked list using System; class GfG { /* Link list Node */ class Node { public int data; public Node next; } // count of nodes static int countOfNodes(Node head) { int count = 0; while (head != null ) { head = head.next; count++; } return count; } // Deletes middle node and returns // head of the modified list static Node deleteMid(Node head) { // Base cases if (head == null ) return null ; if (head.next == null ) { return null ; } // Initialize slow and fast pointers // to reach middle of linked list Node copyHead = head; // Find the count of nodes int count = countOfNodes(head); // Find the middle node int mid = count / 2; // Delete the middle node while (mid-- > 1) { head = head.next; } // Delete the middle node head.next = head.next.next; return copyHead; } // A utility function to print // a given linked list static void printList(Node ptr) { while (ptr != null ) { Console.Write(ptr.data + "->" ); ptr = ptr.next; } Console.WriteLine( "NULL" ); } // Utility function to create a new node. static Node newNode( int data) { Node temp = new Node(); temp.data = data; temp.next = null ; return temp; } /* Driver code*/ public static void Main(String[] args) { /* Start with the empty list */ Node head = newNode(1); head.next = newNode(2); head.next.next = newNode(3); head.next.next.next = newNode(4); Console.WriteLine( "Given Linked List" ); printList(head); head = deleteMid(head); Console.WriteLine( "Linked List after " + "deletion of middle" ); printList(head); } } /* This code is contributed by ShubhamSingh */ |
Javascript
<script> // Javascript program to delete the // middle of a linked list /* Link list Node */ class Node { constructor() { this .data = 0; this .next = null ; } } // count of nodes function countOfNodes(head) { let count = 0; while (head != null ) { head = head.next; count+=1; } return count; } // Deletes middle node and returns // head of the modified list function deleteMid(head) { // Base cases if (head == null ) return null ; if (head.next == null ) { return null ; } var copyHead = head; // Find the count of nodes var count = countOfNodes(head); // Find the middle node var mid = parseInt(count / 2); // Delete the middle node while (mid-- > 1) { head = head.next; } // Delete the middle node head.next = head.next.next; return copyHead; } // A utility function to print // a given linked list function printList( ptr) { while (ptr != null ) { document.write(ptr.data + "->" ); ptr = ptr.next; } document.write( "NULL<br/>" ); } // Utility function to create a new node. function newNode(data) { temp = new Node(); temp.data = data; temp.next = null ; return temp; } /* Driver code */ /* Start with the empty list */ head = newNode(1); head.next = newNode(2); head.next.next = newNode(3); head.next.next.next = newNode(4); document.write( "Given Linked List<br/>" ); printList(head); head = deleteMid(head); document.write( "Linked List after deletion of middle<br/>" ); printList(head); // This code is contributed by Shubham singh </script> |
输出
Given Linked List1->2->3->4->NULLLinked List after deletion of middle1->2->4->NULL
复杂性分析：
- 时间复杂性： O（n）。 需要对链表进行两次遍历
- 辅助空间： O（1）。 不需要额外的空间。
高效的解决方案： 方法： 上述解决方案需要对链表进行两次遍历。中间节点可以通过一次遍历删除。这个想法是使用两个指针，慢速和快速。两个指针都从列表的开头开始。当快速到达终点时，慢速到达中间。这个想法与本文方法2中使用的想法相同 这 邮递这篇文章中的另一件事是跟踪上一个中间节点，以便删除中间节点。
下面是实现。
C++
// C++ program to delete middle // of a linked list #include <bits/stdc++.h> using namespace std; /* Link list Node */ struct Node { int data; struct Node* next; }; // Deletes middle node and returns // head of the modified list struct Node* deleteMid( struct Node* head) { // Base cases if (head == NULL) return NULL; if (head->next == NULL) { delete head; return NULL; } // Initialize slow and fast pointers // to reach middle of linked list struct Node* slow_ptr = head; struct Node* fast_ptr = head; // Find the middle and previous of middle. // To store previous of slow_ptr struct Node* prev; while (fast_ptr != NULL && fast_ptr->next != NULL) { fast_ptr = fast_ptr->next->next; prev = slow_ptr; slow_ptr = slow_ptr->next; } // Delete the middle node prev->next = slow_ptr->next; delete slow_ptr; return head; } // A utility function to print // a given linked list void printList( struct Node* ptr) { while (ptr != NULL) { cout << ptr->data << "->" ; ptr = ptr->next; } cout << "NULL" ; } // Utility function to create a new node. Node* newNode( int data) { struct Node* temp = new Node; temp->data = data; temp->next = NULL; return temp; } /* Driver program to test above function*/ int main() { /* Start with the empty list */ struct Node* head = newNode(1); head->next = newNode(2); head->next->next = newNode(3); head->next->next->next = newNode(4); cout << "Given Linked List" ; printList(head); head = deleteMid(head); cout << "Linked List after deletion of middle" ; printList(head); return 0; } |
JAVA
// Java program to delete the // middle of a linked list class GfG { /* Link list Node */ static class Node { int data; Node next; } // Deletes middle node and returns // head of the modified list static Node deleteMid(Node head) { // Base cases if (head == null ) return null ; if (head.next == null ) { return null ; } // Initialize slow and fast pointers // to reach middle of linked list Node slow_ptr = head; Node fast_ptr = head; // Find the middle and previous of middle. Node prev = null ; // To store previous of slow_ptr while (fast_ptr != null && fast_ptr.next != null ) { fast_ptr = fast_ptr.next.next; prev = slow_ptr; slow_ptr = slow_ptr.next; } // Delete the middle node prev.next = slow_ptr.next; return head; } // A utility function to print // a given linked list static void printList(Node ptr) { while (ptr != null ) { System.out.print(ptr.data + "->" ); ptr = ptr.next; } System.out.println( "NULL" ); } // Utility function to create a new node. static Node newNode( int data) { Node temp = new Node(); temp.data = data; temp.next = null ; return temp; } /* Driver code*/ public static void main(String[] args) { /* Start with the empty list */ Node head = newNode( 1 ); head.next = newNode( 2 ); head.next.next = newNode( 3 ); head.next.next.next = newNode( 4 ); System.out.println( "Given Linked List" ); printList(head); head = deleteMid(head); System.out.println( "Linked List after deletion of middle" ); printList(head); } } // This code is contributed by Prerna saini. |
Python3
# Python3 program to delete the # middle of a linked list # Linked List Node class Node: def __init__( self , data): self .data = data self . next = None # Create and handle list operations class LinkedList: def __init__( self ): # Head of the list self .head = None # Add new node to the list end def addToList( self , data): newNode = Node(data) if self .head is None : self .head = newNode return last = self .head while last. next : last = last. next last. next = newNode # Returns the list in string format def __str__( self ): linkedListStr = "" temp = self .head while temp: linkedListStr + = str (temp.data) + "->" temp = temp. next return linkedListStr + "NULL" # Method deletes middle node def deleteMid( self ): # Base cases if ( self .head is None or self .head. next is None ): return # Initialize slow and fast pointers # to reach middle of linked list slow_Ptr = self .head fast_Ptr = self .head # Find the middle and previous of middle prev = None # To store previous of slow pointer while (fast_Ptr is not None and fast_Ptr. next is not None ): fast_Ptr = fast_Ptr. next . next prev = slow_Ptr slow_Ptr = slow_Ptr. next # Delete the middle node prev. next = slow_Ptr. next # Driver code linkedList = LinkedList() linkedList.addToList( 1 ) linkedList.addToList( 2 ) linkedList.addToList( 3 ) linkedList.addToList( 4 ) print ( "Given Linked List" ) print (linkedList) linkedList.deleteMid() print ( "Linked List after deletion of middle" ) print (linkedList) # This code is contributed by Debidutta Rath |
C#
// C# program to delete middle of a linked list using System; class GfG { /* Link list Node */ class Node { public int data; public Node next; } // Deletes middle node and returns // head of the modified list static Node deleteMid(Node head) { // Base cases if (head == null ) return null ; if (head.next == null ) { return null ; } // Initialize slow and fast pointers // to reach middle of linked list Node slow_ptr = head; Node fast_ptr = head; // Find the middle and previous of middle. Node prev = null ; // To store previous of slow_ptr while (fast_ptr != null && fast_ptr.next != null ) { fast_ptr = fast_ptr.next.next; prev = slow_ptr; slow_ptr = slow_ptr.next; } // Delete the middle node prev.next = slow_ptr.next; return head; } // A utility function to print // a given linked list static void printList(Node ptr) { while (ptr != null ) { Console.Write(ptr.data + "->" ); ptr = ptr.next; } Console.WriteLine( "NULL" ); } // Utility function to create a new node. static Node newNode( int data) { Node temp = new Node(); temp.data = data; temp.next = null ; return temp; } /* Driver code*/ public static void Main(String[] args) { /* Start with the empty list */ Node head = newNode(1); head.next = newNode(2); head.next.next = newNode(3); head.next.next.next = newNode(4); Console.WriteLine( "Given Linked List" ); printList(head); head = deleteMid(head); Console.WriteLine( "Linked List after" + "deletion of middle" ); printList(head); } } /* This code is contributed by 29AjayKumar */ |
Javascript
<script> // Javascript program to delete the // middle of a linked list /* Link list Node */ class Node { constructor() { this .data = 0; this .next = null ; } } // Deletes middle node and returns // head of the modified list function deleteMid( head) { // Base cases if (head == null ) return null ; if (head.next == null ) { return null ; } // Initialize slow and fast pointers // to reach middle of linked list var slow_ptr = head; var fast_ptr = head; // Find the middle and previous of middle. var prev = null ; // To store previous of slow_ptr while (fast_ptr != null && fast_ptr.next != null ) { fast_ptr = fast_ptr.next.next; prev = slow_ptr; slow_ptr = slow_ptr.next; } // Delete the middle node prev.next = slow_ptr.next; return head; } // A utility function to print // a given linked list function printList( ptr) { while (ptr != null ) { document.write(ptr.data + "->" ); ptr = ptr.next; } document.write( "NULL<br/>" ); } // Utility function to create a new node. function newNode(data) { temp = new Node(); temp.data = data; temp.next = null ; return temp; } /* Driver code */ /* Start with the empty list */ head = newNode(1); head.next = newNode(2); head.next.next = newNode(3); head.next.next.next = newNode(4); document.write( "Given Linked List<br/>" ); printList(head); head = deleteMid(head); document.write( "Linked List after deletion of middle<br/>" ); printList(head); // This code contributed by umadevi9616 </script> |
输出
Given Linked List1->2->3->4->NULLLinked List after deletion of middle1->2->4->NULL
复杂性分析：
- 时间复杂性： O（n）。 只需要遍历链表一次
- 辅助空间： O（1）。 因为不需要额外的空间。
-7rw？list=PLqM7alHXFySH41ZxzrPNj2pAYPOI8ITe7 本文由 皮尤斯·古普塔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以写一篇文章，然后将文章邮寄给评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
