04 链表的删除：删除链表中指定位置的元素（Linked List 链表）

梦里梦外; 2021-12-24 03:49 476阅读 0赞

> 采用C语言实现：完整删除链表中指定位置的元素的代码。

原链表：3->4->5。现在要删除位置为2处的元素。  
删除后的链表：3->5。

#include <stdio.h>
    #include <stdlib.h>
    #include <MacTypes.h>
    
    /*定义节点*/
    typedef struct Node {
        int data;
        struct Node *next;
    } LinkedList;
    
    /*使用头插法来构建一个链表*/
    void push(struct Node **head_ref, int new_data);
    
    /*给一个指针的指针作为引用，作为这个链表的头指针,进行删除指定位置的节点*/
    void deleteNode(struct Node **head_ref, int position);
    
    /*打印链表*/
    void printList(LinkedList *node);
    
    int main() {
        LinkedList *head_ref = NULL;
        //注意这里要传取地址符
        push(&head_ref, 3);
        push(&head_ref, 4);
        push(&head_ref, 5);
        deleteNode(&head_ref,2);
        printList(head_ref);
        return 0;
    }
    
    /*
     * 头插法的几步
     * 1.定义一个新的指针，给指针申请空间，使其变成一个新的节点。
     * 2.给这个新的节点data数据域赋值。
     * 3.将这个新的节点的next指针指向原来的开始节点（原头指针指向的节点）
     * 4.将原头指针左移移动到新的节点
     */
    void push(struct Node **head_ref, int new_data) {
    
        LinkedList *new_node = (LinkedList *) malloc(sizeof(LinkedList));
        new_node->data = new_data;
        new_node->next = (*head_ref);
        (*head_ref) = new_node;
    }
    
    /*从给定节点往后打印链表*/
    void printList(LinkedList *node) {
        //节点不为空，循环
        while (node != NULL) {
            //打印节点值
            printf(" %d \n", node->data);
            //指针后移
            node = node->next;
        }
    }
    
    /*删除指定位置的的节点*/
    void deleteNode(struct Node **head_ref, int position) {
    
        //1.首先判断这个链表是否为空
        if (*head_ref == NULL) {
            return;
        }
    
        //2.创建一个指针存储头节点
        struct Node *temp = *head_ref;
    
        //3.如果这个position是0，那么直接移除掉头节点
        if (position == 0) {
            *head_ref = temp->next;
            free(temp);
            return;
        }
    
        //4.从头节点遍历，找到删除位置position的前驱节点,temp指向前驱
        for (int i = 0; temp != NULL && i < position - 1; ++i) {
            temp = temp->next;
        }
    
        //5.如果这个位置比链表还长
        if (temp == NULL || temp ->next == NULL){
            return;
        }
    
        //6.创建一个新的指针指向将要删除的节点的下一个节点
        //temp是删除节点的前驱
        //temp->next 这个节点是即将被删除的节点
        struct Node *next = temp->next->next;
        //7.删除节点
        free(temp->next);
    
        //8.将next节点连接在前驱节点temp后面
        temp->next=next;
    
    }

输出：

5 
     4