给定一个单链表和一个位置,删除给定位置的一个链表节点。
例子:
输入:位置 = 1,链表 = 8->2->3->1->7 输出:链表 = 8->3->1->7 输入:位置 = 0,链表 = 8->2->3->1->7 输出:链表 = 2->3->1->7
如果要删除的节点是根节点,直接删除即可。要删除中间节点,我们必须有一个指向要删除的节点之前的节点的指针。因此,如果位置不为零,我们将循环 position-1 次并获得指向前一个节点的指针。
下面是上述想法的实现。
#include <iostream> using namespace std; class Node { public: int data; Node *next; }; 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; } void deleteNode(Node **head_ref, int position) { if (*head_ref == NULL) return; Node* temp = *head_ref; if (position == 0) { *head_ref = temp->next; free(temp); return; } for(int i = 0; temp != NULL && i < position - 1; i++) temp = temp->next; if (temp == NULL || temp->next == NULL) return; Node *next = temp->next->next; free(temp->next); temp->next = next; } void printList( Node *node) { while (node != NULL) { cout << node->data << " "; node = node->next; } } int main() { Node* head = NULL; push(&head, 7); push(&head, 1); push(&head, 3); push(&head, 2); push(&head, 8); cout << "创建的链表:"; printList(head); deleteNode(&head, 4); cout << "\n位置 4 删除后的链表:"; printList(head); return 0; }
输出:
创建的链表: 8 2 3 1 7 位置 4 删除后的链表: 8 2 3 1