删除单链表中的倒数第k个结点

你的名字 2022-05-24 00:00 164阅读 0赞

**       算法思想**：定义两个指针，pFast和pSlow，都指向头结点，pFast先后移k-1位，使pFast指向第k个结点，此时pSlow就是相对pFast的倒数第k个结点。然后同时后移，当pFast走到表尾时，pSlow正好指向倒数第k个结点。然后将pSlow指向的结点删除。

删除单链表中的倒数第k个结点，首先要确定倒数第k个结点的位置。

![20180516195739614][]

//查找指向链表中的倒数第k个结点的指针
    
    Node* Find_k_Node(LinkList pHead, int k)
    {
    	if (pHead == NULL || k < 0)
    	{
    		return NULL;
    	}
    	Node* pFast = pHead;
    	Node* pSlow = pHead;
    	//pFast指针后移k-1位
    	while (--k)
    	{
    		pFast = pFast->Next;
    	}
    	//循环结束后pFast指向表尾，pSlow指向链表的倒数第k个结点
    	while (pHead&&(pFast->Next))
    	{
    		pSlow = pSlow->Next;
    		pFast = pFast->Next;
    	}
    	//返回指向倒数第k个结点的指针
    	return pSlow;
    }

![20180516201348324][]

//删除链表中的倒数第k个结点
    int Del_k_Node(LinkList pHead, int k)
    {
    	if (k < 1 || k > length(pHead))
    	{
    		printf("input error!\n");
    		return NULL;
    	}
    	//调用Find_k_Node，得到指向倒数第k个结点的指针
    	Node* pDel = Find_k_Node(pHead, k);
    	Node* pPre = pHead;
    	Node* pNext = pDel->Next;
    	//使pPre从pHead开始后移，循环结束时，pPre->Next=pDl;
    	while (pPre->Next != pDel)
    	{
    		pPre = pPre->Next;
    	}
    	pPre->Next = pNext;
    	free(pDel);
    	//打印删除倒数第k个结点后链表中的元素
    	PrintList(pHead);
    	return 0;
    }

**完整源代码：**

#include <stdio.h>
    #include <Windows.h>
    #include <stdlib.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;
    }
    //求表长，求链表中元素的个数
    
    int length(LinkList pHead)
    {
    	if (pHead == NULL)
    	{
    		return 0;
    	}
    	int count = 0;
    	Node* p;
    	p = pHead;
    	while (p)
    	{
    		p = p->Next;
    		count++;
    	}
    	return count;
    }
    
    //打印表中元素
    
    void PrintList(LinkList pHead)
    {
    	Node* pCur = pHead;
    	while (pCur)
    	{
    		printf("%-3d", pCur->Data);
    		pCur = pCur->Next;
    	}
    	printf("\n");
    }
    //查找指向链表中的倒数第k个结点的指针
    
    Node* Find_k_Node(LinkList pHead, int k)
    {
    	if (pHead == NULL || k < 0)
    	{
    		return NULL;
    	}
    	Node* pFast = pHead;
    	Node* pSlow = pHead;
    	//pFast指针后移k-1位
    	while (--k)
    	{
    		pFast = pFast->Next;
    	}
    	//循环结束后pFast指向表尾，pSlow指向链表的倒数第k个结点
    	while (pHead && (pFast->Next))
    	{
    		pSlow = pSlow->Next;
    		pFast = pFast->Next;
    	}
    	//返回指向倒数第k个结点的指针
    	return pSlow;
    }
    
    //删除链表中的倒数第k个结点
    int Del_k_Node(LinkList pHead, int k)
    {
    	if (k < 1 || k > length(pHead))
    	{
    		printf("input error!\n");
    		return NULL;
    	}
    	//调用Find_k_Node，得到指向倒数第k个结点的指针
    	Node* pDel = Find_k_Node(pHead, k);
    	Node* pPre = pHead;
    	Node* pNext = pDel->Next;
    	//使pPre从pHead开始后移，循环结束时，pPre->Next=pDl;
    	while (pPre->Next != pDel)
    	{
    		pPre = pPre->Next;
    	}
    	pPre->Next = pNext;
    	free(pDel);
    	//打印删除倒数第k个结点后链表中的元素
    	PrintList(pHead);
    	return 0;
    }
    
    int main()
    {
    	LinkList L;
    	//初使化链表
    	InitList(&L);
    	int k = 0;
    	int data = 0;
    	scanf("%d", &data);
    	//在链表中循环插入元素data，以-1作为结束标志
    	while (data != -1)
    	{
    		PushBack(&L, data);
    		scanf("%d", &data);
    	}
    	//打印表中元素
    	PrintList(L);
    	//输入要删除的元素序号k，倒数
    	scanf("%d", &k);
    	//删除表L中的倒数第k个结点，并打印删除后链表中的元素
    	Del_k_Node(L, k);
    	system("pause");
    	return 0;
    }

[20180516195739614]: /images/20220524/3965c00daade4fbebebccfaa80c2ff26.png
[20180516201348324]: /images/20220524/9efc816580de466e8e93249c4b3ab9d0.png