设一个没有头结点指针的单链表。一个指针指向此单链表中间的一个结点（不是第一个，也不是最后一个结点），将该结点从单链表中删除，要求时间复杂度O（1）

妖狐艹你老母 2022-05-25 14:26 111阅读 0赞

> 问题：设一个没有头结点指针的单链表。一个指针指向此单链表中间的一个结点（不是第一个，也不是最后一个结点），将该结点从单链表中删除，要求时间复杂度O（1）

--------------------

![这里写图片描述][70]  
       详细描述这一过程：  
![这里写图片描述][70 1]

--------------------

//删除链表中pDel指向的结点
    void Delete(LinkList* pHead, Node* pDel)
    {
        Node* pCur ;
        pCur = pDel->Next;
        pDel->Data = pCur->Data;
        pDel->Next = pCur->Next;
        free(pCur);
    }

删除pDel指向的结点，我们先要确定pDel的位置，定义函数`Node* GetNode(LinkList pHead,int n)`用于返回指向要删除结点的指针，返回值作函数`void Delete(LinkList* pHead, Node* pDel)`中的pDel参数。

//返回指向第n个结点的指针
    Node* GetNode(LinkList pHead,int n) 
    {
        Node* pCur = pHead;
        while (pCur&&--n)
        {
            pCur = pCur->Next;
        }
        return pCur;
    }

**完整源代码：**

#include <stdio.h>
    #include <Windows.h>
    
    typedef int DataType;
    
    typedef struct Node
    {
        DataType Data;
        struct Node* Next;
    }Node, *LinkList;
    
    //初始化，将头指针pHead置空
    void InitList(LinkList* pHead)
    {
        *pHead = NULL;
    }
    
    //尾插，在表尾插入一个元素data
    
    void PushBack(LinkList* pHead, DataType data)
    {
        //如果链表为空，则在表头插入元素data
        if (NULL == (*pHead))
        {
            *pHead = (LinkList)malloc(sizeof(Node));
            if (NULL == *pHead)
            {
                printf("申请空间失败!\n");
            }
            (*pHead)->Data = data;
            (*pHead)->Next = NULL;
            /*PushFornt(pHead, data);*/
            return;
        }
    
        Node* pCur = (*pHead);
    
        Node* pNewNode = (LinkList)malloc(sizeof(Node));
        if (pNewNode == NULL)
        {
            printf("申请空间失败!\n");
        }
        //跳出循环时pCur指向链表的尾结点
        while (pCur->Next != NULL)
        {
            pCur = pCur->Next;
        }
        pNewNode->Data = data;
        pCur->Next = pNewNode;
        pNewNode->Next = NULL;
    }
    
    //打印表中元素
    
    void PrintList(LinkList pHead)
    {
        Node* pCur = pHead;
        while (pCur)
        {
            printf("%-3d", pCur->Data);
            pCur = pCur->Next;
        }
        printf("\n");
    }
    
    //删除链表中pDel指向的结点
    void Delete(LinkList* pHead, Node* pDel)
    {
        Node* pCur ;
        pCur = pDel->Next;
        pDel->Data = pCur->Data;
        pDel->Next = pCur->Next;
        free(pCur);
    }
    
    //返回指向第n个结点的指针
    Node* GetNode(LinkList pHead,int n) 
    {
        Node* pCur = pHead;
        while (pCur&&--n)
        {
            pCur = pCur->Next;
        }
        return pCur;
    }
    int main()
    {
        LinkList L = NULL;
        int data = 0;
        int num = 0;    //要删除结点的序号
        //初始化电脑链表
        InitList(&L);
        scanf("%d", &data);
        //使用尾插法，向链表中插入元素，以-1作为结束标志
        while (data != -1)
        {
            PushBack(&L, data);
            scanf("%d", &data);
        }
        //打印插入链表中的元素
        PrintList(L);
        //输入要删除的结点序号
        scanf("%d", &num);
        //调用GetNode函数返回要删除指向要删除结点的指针
        Node* p = GetNode(L,num); 
        //删除p结点
        Delete(&L,p);
        //打印删除p指针指向结点后链表表中元素
        PrintList(L);
        system("pause");
        return 0;
    }

[70]: /images/20220525/5b0aab3f7e754a3a861e56538814468c.png
[70 1]: /images/20220525/2f13bd3d1f114695b6dcc9b1fe2fe2b3.png