给定一个单链表，编写一个函数来删除给定的节点。您的函数必须遵循以下约束： 1） 它必须接受指向起始节点的指针作为第一个参数，将要删除的节点作为第二个参数，即指向头节点的指针不是全局的。 2） 它不应该返回指向头部节点的指针。 3） 它不应该接受指向头部节点的指针。 你可以假设链表永远不会变成空的。 函数名为deleteNode（）。在简单的实现中，当要删除的节点是第一个节点时，函数需要修改头指针。如中所述 以前的职位 ，当函数修改头指针时，该函数必须使用 给定的方法 ，我们不能使用这些方法中的任何一种。 解决方案 我们显式地处理要删除的节点是第一个节点的情况，我们将下一个节点的数据复制到head并删除下一个节点。当删除的节点不是头节点时，可以通过查找前一个节点并更改前一个节点的下一个节点来正常处理。以下是实现。
null
C++
// C++ program to delete a given node // in linked list under given constraints #include <bits/stdc++.h> using namespace std; /* structure of a linked list node */ class Node { public : int data; Node *next; }; void deleteNode(Node *head, Node *n) { // When node to be deleted is head node if (head == n) { if (head->next == NULL) { cout << "There is only one node." << " The list can't be made empty " ; return ; } /* Copy the data of next node to head */ head->data = head->next->data; // store address of next node n = head->next; // Remove the link of next node head->next = head->next->next; // free memory free (n); return ; } // When not first node, follow // the normal deletion process // find the previous node Node *prev = head; while (prev->next != NULL && prev->next != n) prev = prev->next; // Check if node really exists in Linked List if (prev->next == NULL) { cout << "Given node is not present in Linked List" ; return ; } // Remove node from Linked List prev->next = prev->next->next; // Free memory free (n); return ; } /* Utility function to insert a node at the beginning */ void push(Node **head_ref, int new_data) { Node *new_node = new Node(); new_node->data = new_data; new_node->next = *head_ref; *head_ref = new_node; } /* Utility function to print a linked list */ void printList(Node *head) { while (head!=NULL) { cout<<head->data<< " " ; head=head->next; } cout<<endl; } /* Driver code */ int main() { Node *head = NULL; /* Create following linked list 12->15->10->11->5->6->2->3 */ push(&head,3); push(&head,2); push(&head,6); push(&head,5); push(&head,11); push(&head,10); push(&head,15); push(&head,12); cout<< "Given Linked List: " ; printList(head); /* Let us delete the node with value 10 */ cout<< "Deleting node " << head->next->next->data<< " " ; deleteNode(head, head->next->next); cout<< "Modified Linked List: " ; printList(head); /* Let us delete the first node */ cout<< "Deleting first node " ; deleteNode(head, head); cout<< "Modified Linked List: " ; printList(head); return 0; } // This code is contributed by rathbhupendra |
C
#include <stdio.h> #include <stdlib.h> /* structure of a linked list node */ struct Node { int data; struct Node *next; }; void deleteNode( struct Node *head, struct Node *n) { // When node to be deleted is head node if (head == n) { if (head->next == NULL) { printf ( "There is only one node. The list can't be made empty " ); return ; } /* Copy the data of next node to head */ head->data = head->next->data; // store address of next node n = head->next; // Remove the link of next node head->next = head->next->next; // free memory free (n); return ; } // When not first node, follow the normal deletion process // find the previous node struct Node *prev = head; while (prev->next != NULL && prev->next != n) prev = prev->next; // Check if node really exists in Linked List if (prev->next == NULL) { printf ( " Given node is not present in Linked List" ); return ; } // Remove node from Linked List prev->next = prev->next->next; // Free memory free (n); return ; } /* Utility function to insert a node at the beginning */ void push( struct Node **head_ref, int new_data) { struct Node *new_node = ( struct Node *) malloc ( sizeof ( struct Node)); new_node->data = new_data; new_node->next = *head_ref; *head_ref = new_node; } /* Utility function to print a linked list */ void printList( struct Node *head) { while (head!=NULL) { printf ( "%d " ,head->data); head=head->next; } printf ( "" ); } /* Driver program to test above functions */ int main() { struct Node *head = NULL; /* Create following linked list 12->15->10->11->5->6->2->3 */ push(&head,3); push(&head,2); push(&head,6); push(&head,5); push(&head,11); push(&head,10); push(&head,15); push(&head,12); printf ( "Given Linked List: " ); printList(head); /* Let us delete the node with value 10 */ printf ( "Deleting node %d: " , head->next->next->data); deleteNode(head, head->next->next); printf ( "Modified Linked List: " ); printList(head); /* Let us delete the first node */ printf ( "Deleting first node " ); deleteNode(head, head); printf ( "Modified Linked List: " ); printList(head); getchar (); return 0; } |
Python 3
# Node class class Node: def __init__( self , data): self .data = data self . next = None # LinkedList class class LinkedList: def __init__( self ): self .head = None def deleteNode( self , data): temp = self .head prev = self .head if temp.data = = data: if temp. next is None : print ( "Can't delete the node as it has only one node" ) else : temp.data = temp. next .data temp. next = temp. next . next return while temp. next is not None and temp.data ! = data: prev = temp temp = temp. next if temp. next is None and temp.data ! = data: print ( "Can't delete the node as it doesn't exist" ) # If node is last node of the linked list elif temp. next is None and temp.data = = data: prev. next = None else : prev. next = temp. next # To push a new element in the Linked List def push( self , new_data): new_node = Node(new_data) new_node. next = self .head self .head = new_node # To print all the elements of the Linked List def PrintList( self ): temp = self .head while (temp): print (temp.data, end = " " ) temp = temp. next # Driver Code llist = LinkedList() llist.push( 3 ) llist.push( 2 ) llist.push( 6 ) llist.push( 5 ) llist.push( 11 ) llist.push( 10 ) llist.push( 15 ) llist.push( 12 ) print ( "Given Linked List: " , end = ' ' ) llist.PrintList() print ( "Deleting node 10:" ) llist.deleteNode( 10 ) print ( "Modified Linked List: " , end = ' ' ) llist.PrintList() print ( "Deleting first node" ) llist.deleteNode( 12 ) print ( "Modified Linked List: " , end = ' ' ) llist.PrintList() # This code is contributed by Akarsh Somani |
JAVA
// Java program to delete a given node // in linked list under given constraints class LinkedList { static Node head; static class Node { int data; Node next; Node( int d) { data = d; next = null ; } } void deleteNode(Node node, Node n) { // When node to be deleted is head node if (node == n) { if (node.next == null ) { System.out.println( "There is only one node. The list " + "can't be made empty " ); return ; } /* Copy the data of next node to head */ node.data = node.next.data; // store address of next node n = node.next; // Remove the link of next node node.next = node.next.next; // free memory System.gc(); return ; } // When not first node, follow the normal deletion process // find the previous node Node prev = node; while (prev.next != null && prev.next != n) { prev = prev.next; } // Check if node really exists in Linked List if (prev.next == null ) { System.out.println( "Given node is not present in Linked List" ); return ; } // Remove node from Linked List prev.next = prev.next.next; // Free memory System.gc(); return ; } /* Utility function to print a linked list */ void printList(Node head) { while (head != null ) { System.out.print(head.data + " " ); head = head.next; } System.out.println( "" ); } public static void main(String[] args) { LinkedList list = new LinkedList(); list.head = new Node( 12 ); list.head.next = new Node( 15 ); list.head.next.next = new Node( 10 ); list.head.next.next.next = new Node( 11 ); list.head.next.next.next.next = new Node( 5 ); list.head.next.next.next.next.next = new Node( 6 ); list.head.next.next.next.next.next.next = new Node( 2 ); list.head.next.next.next.next.next.next.next = new Node( 3 ); System.out.println( "Given Linked List :" ); list.printList(head); System.out.println( "" ); // Let us delete the node with value 10 System.out.println( "Deleting node :" + head.next.next.data); list.deleteNode(head, head.next.next); System.out.println( "Modified Linked list :" ); list.printList(head); System.out.println( "" ); // Let us delete the first node System.out.println( "Deleting first Node" ); list.deleteNode(head, head); System.out.println( "Modified Linked List" ); list.printList(head); } } // this code has been contributed by Mayank Jaiswal |
C#
// C# program to delete a given // node in linked list under // given constraints using System; public class LinkedList { Node head; class Node { public int data; public Node next; public Node( int d) { data = d; next = null ; } } void deleteNode(Node node, Node n) { // When node to be deleted is head node if (node == n) { if (node.next == null ) { Console.WriteLine( "There is only one node. The list " + "can't be made empty " ); return ; } /* Copy the data of next node to head */ node.data = node.next.data; // store address of next node n = node.next; // Remove the link of next node node.next = node.next.next; // free memory GC.Collect(); return ; } // When not first node, follow // the normal deletion process // find the previous node Node prev = node; while (prev.next != null && prev.next != n) { prev = prev.next; } // Check if node really exists in Linked List if (prev.next == null ) { Console.WriteLine( "Given node is not" + "present in Linked List" ); return ; } // Remove node from Linked List prev.next = prev.next.next; // Free memory GC.Collect(); return ; } /* Utility function to print a linked list */ void printList(Node head) { while (head != null ) { Console.Write(head.data + " " ); head = head.next; } Console.WriteLine( "" ); } // Driver code public static void Main(String[] args) { LinkedList list = new LinkedList(); list.head = new Node(12); list.head.next = new Node(15); list.head.next.next = new Node(10); list.head.next.next.next = new Node(11); list.head.next.next.next.next = new Node(5); list.head.next.next.next.next.next = new Node(6); list.head.next.next.next.next.next.next = new Node(2); list.head.next.next.next.next.next.next.next = new Node(3); Console.WriteLine( "Given Linked List :" ); list.printList(list.head); Console.WriteLine( "" ); // Let us delete the node with value 10 Console.WriteLine( "Deleting node :" + list.head.next.next.data); list.deleteNode(list.head, list.head.next.next); Console.WriteLine( "Modified Linked list :" ); list.printList(list.head); Console.WriteLine( "" ); // Let us delete the first node Console.WriteLine( "Deleting first Node" ); list.deleteNode(list.head, list.head); Console.WriteLine( "Modified Linked List" ); list.printList(list.head); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // javascript program to delete a given node // in linked list under given constraints var head; class Node { constructor(val) { this .data = val; this .next = null ; } } function deleteNode( node, n) { // When node to be deleted is head node if (node == n) { if (node.next == null ) { document.write( "There is only one node. The list " + "can't be made empty " ); return ; } /* Copy the data of next node to head */ node.data = node.next.data; // store address of next node n = node.next; // Remove the link of next node node.next = node.next.next; // free memory return ; } // When not first node, follow the normal deletion process // find the previous node prev = node; while (prev.next != null && prev.next != n) { prev = prev.next; } // Check if node really exists in Linked List if (prev.next == null ) { document.write( "Given node is not present in Linked List" ); return ; } // Remove node from Linked List prev.next = prev.next.next; return ; } /* Utility function to print a linked list */ function printList( head) { while (head != null ) { document.write(head.data + " " ); head = head.next; } document.write( "" ); } head = new Node(12); head.next = new Node(15); head.next.next = new Node(10); head.next.next.next = new Node(11); head.next.next.next.next = new Node(5); head.next.next.next.next.next = new Node(6); head.next.next.next.next.next.next = new Node(2); head.next.next.next.next.next.next.next = new Node(3); document.write( "Given Linked List :" ); printList(head); document.write( "" ); // Let us delete the node with value 10 document.write( "<br/>Deleting node :" + head.next.next.data); deleteNode(head, head.next.next); document.write( "<br/>Modified Linked list :" ); printList(head); document.write( "<br/>" ); // Let us delete the first node document.write( "Deleting first Node<br/>" ); deleteNode(head, head); document.write( "Modified Linked List" ); printList(head); // This code is contributed by todaysgaurav </script> |
输出：
Given Linked List: 12 15 10 11 5 6 2 3Deleting node 10:Modified Linked List: 12 15 11 5 6 2 3Deleting first nodeModified Linked List: 15 11 5 6 2 3
如果您发现上述代码/算法不正确，请写下评论，或者寻找其他方法来解决相同的问题。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
