从列表中删除大于x的所有节点-yiteyi-C++库

给定一个链表，问题是从列表中删除所有大于指定值的节点十、 .

null

例如：

Input : list: 7->3->4->8->5->1
        x = 6
Output : 3->4->5->1

Input : list: 1->8->7->3->7->10
        x = 7
Output : 1->7->3->7

资料来源： 微软面试经验|设定169。

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

方法： 这主要是帖子的一个变体删除给定密钥的第一个匹配项。

我们需要首先检查头部节点上大于“x”的所有事件，删除它们并适当更改头部节点。然后我们需要检查循环中的所有事件，并逐个删除它们。

                     // C++ implementation to delete all the nodes from the list                   
                     // that are greater than the specified value x                   
                     #include <bits/stdc++.h>                   
                             
                     using                               namespace                               std;                   
                             
                     // structure of a node                   
                     struct                               Node {                   
                                         int                               data;                   
                                         Node* next;                   
                     };                   
                             
                     // function to get a new node                   
                     Node* getNode(                               int                               data)                   
                     {                   
                                         Node* newNode =                               new                               Node;                   
                                         newNode->data = data;                   
                                         newNode->next = NULL;                   
                                         return                               newNode;                   
                     }                   
                             
                     // function to delete all the nodes from the list                   
                     // that are greater than the specified value x                   
                     void                               deleteGreaterNodes(Node** head_ref,                               int                               x)                   
                     {                   
                                         Node *temp = *head_ref, *prev;                   
                             
                                         // If head node itself holds the value greater than 'x'                   
                                         if                               (temp != NULL && temp->data > x) {                   
                                         *head_ref = temp->next;                               // Changed head                   
                                         free                               (temp);                               // free old head                   
                                         temp = *head_ref;                               // Change temp                   
                                         }                   
                             
                                         // Delete occurrences other than head                   
                                         while                               (temp != NULL) {                   
                             
                                         // Search for the node to be deleted,                   
                                         // keep track of the previous node as we                   
                                         // need to change 'prev->next'                   
                                         while                               (temp != NULL && temp->data <= x) {                   
                                         prev = temp;                   
                                         temp = temp->next;                   
                                         }                   
                             
                                         // If required value node was not present                   
                                         // in linked list                   
                                         if                               (temp == NULL)                   
                                         return                               ;                   
                             
                                         // Unlink the node from linked list                   
                                         prev->next = temp->next;                   
                             
                                         delete                               temp;                               // Free memory                   
                             
                                         // Update Temp for next iteration of                   
                                         // outer loop                   
                                         temp = prev->next;                   
                                         }                   
                     }                   
                             
                     // function to a print a linked list                   
                     void                               printList(Node* head)                   
                     {                   
                                         while                               (head) {                   
                                         cout << head->data <<                               " "                               ;                   
                                         head = head->next;                   
                                         }                   
                     }                   
                             
                     // Driver program to test above                   
                     int                               main()                   
                     {                   
                                         // Create list: 7->3->4->8->5->1                   
                                         Node* head = getNode(7);                   
                                         head->next = getNode(3);                   
                                         head->next->next = getNode(4);                   
                                         head->next->next->next = getNode(8);                   
                                         head->next->next->next->next = getNode(5);                   
                                         head->next->next->next->next->next = getNode(1);                   
                             
                                         int                               x = 6;                   
                             
                                         cout <<                               "Original List: "                               ;                   
                                         printList(head);                   
                             
                                         deleteGreaterNodes(&head, x);                   
                             
                                         cout <<                               "Modified List: "                               ;                   
                                         printList(head);                   
                             
                                         return                               0;                   
                     }                   

输出：

Original List: 7 3 4 8 5 1 
Modified List: 3 4 5 1

时间复杂度：O（n）。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章